| 网站首页 | 业界新闻 | 小组 | 交易 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
共有 144 人关注过本帖
标题:素数问题 c++
只看楼主 加入收藏
qiansu
Rank: 1
等 级:新手上路
帖 子:7
专家分:0
注 册:2021-6-22
结帖率:50%
收藏
已结贴  问题点数:20 回复次数:5 
素数问题 c++
Problem Description
今天,小猪猪学习了新的知识,孤儿数,孤儿数就是除了1和他本身,其他数都不是他的因子.他发现,这些孤儿数的分布是有规律的,如果一个区间[l,r]中有超过1/3的孤儿数,那这个区间就是孤儿区间.你知道怎么判断一个区间是不是孤儿区间吗?
Input
第一行:T,表示有T组数据(T<=10);

下面T行,每行两个数字l,r,你需要判断[l,r]是不是一个孤儿区间.

(l,r<1e9,当l>=1000时,保证区间长度>=100,所以你可不能暴力求素数哦!)
这里提供一个筛素数的模板,你可能需要用,用法如下,(仔细点别抄错了...):
/*
* 素数筛选,判断小于 MAXN 的数是不是素数。
* notprime 是一张表,为 false 表示是素数,true 表示不是素数
*/
const int MAXN=1000010;
bool notprime[MAXN];//值为 false 表示素数,值为 true 表示非素数
void init() {
  memset(notprime,false,sizeof(notprime)); //需要#include<string.h>头文件
  notprime[0]=notprime[1]=true;
  for(int i=2; i<MAXN; i++)
    if(!notprime[i]) {
      if(i>MAXN/i)continue;
      for(int j=i*i; j<MAXN; j+=i)
        notprime[j]=true;
    }
}



int main(){
init();
/*------这里写你的代码....*/
}

Output
如果区间是孤儿区间,输出"YES",否则输出"NO"
Sample Input
1
2 3
Sample Output
YES




搜索更多相关主题的帖子: 表示 int 区间 c++ 素数 
2021-09-13 20:26
qiansu
Rank: 1
等 级:新手上路
帖 子:7
专家分:0
注 册:2021-6-22
收藏
得分:0 
这个题目的输入案例太少了 给我整烦死
2021-09-13 20:26
qiansu
Rank: 1
等 级:新手上路
帖 子:7
专家分:0
注 册:2021-6-22
收藏
得分:0 

#include <bits/stdc++.h>
using namespace std;
#define re register
#define ll long long
const int maxn=1e6+1;
ll l,r;
int prime[maxn],cnt,ans;
bool vis[maxn];
inline void Gprime()
{
    for(re int i=2;i<=50000;++i)
    {
        if(!vis[i])prime[++cnt]=i;
        for(re int j=1;i*prime[j]<=50000;j++)
        {
            vis[i*prime[j]]=1;
            if(i%prime[j]==0) break;
        }
    }
}

ll shuru(){
   
   
 ios::sync_with_stdio(false);
    //cin>>l>>r;
    l=l==1?2:l;
    Gprime();
    memset(vis,0,sizeof(vis));
    for(re int i=1;i<=cnt;++i)
    {
        ll p=prime[i],start=(l+p-1)/p*p>2*p?(l+p-1)/p*p:2*p;
        for(re ll int j=start;j<=r;j+=p)vis[j-l+1]=1;
    }
    for(re int i=1;i<=r-l+1;++i)if(!vis[i])ans++;
    //cout<<ans;
 
    return ans;
   
}

int t;
bool res[100];

int main()
{
    cin>>t;
    for(int i=0;i<t;i++){
        cin>>l>>r;
        int all=r-l+1;
       // cout<<shuru();
       //cout<<all<<endl;
       //cout<<shuru()<<endl;
        if(shuru()*3>all) res[i]=true;
        else res[i]=false;
    }
    for(int i=0;i<t;i++){
        if(res[i]) cout<<"YES"<<" ";
        else cout<<"NO"<<" ";
    }

   
}


大可不用看我的代码
2021-09-13 20:30
不会游泳的虾
Rank: 2
等 级:论坛游民
威 望:1
帖 子:9
专家分:33
注 册:2021-7-1
收藏
得分:10 
供参考:
程序代码:
//Sample Input
//1
//2 3
//Sample Output
//YES
#include <stdio.h>
#include <string.h>
/*
* 素数筛选,判断小于 MAXN 的数是不是素数。
* notprime 是一张表,为 false 表示是素数,true 表示不是素数
*/
const int MAXN = 1e9-1;
bool   notprime[MAXN];//值为 false 表示素数,值为 true 表示非素数
void init() {
    memset(notprime, false, sizeof(notprime)); //需要#include<string.h>头文件
    notprime[0] = notprime[1] = 1;
    for (int i = 2; i < MAXN; i++)
        if (!notprime[i]) {
            if (i > MAXN / i)continue;
            for (int j = i * i; j < MAXN; j += i)
                notprime[j] = true;
        }
}
int main() 
{
    init();
    /*------这里写你的代码....*/
    int T, l, r, i, cnt;
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &l, &r);
        cnt = 0;
        for (i = l; i <= r; i++)
            if (!notprime[i])cnt++;
        if (cnt > (r - l + 1) / 3)
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}
2021-09-14 10:20
diycai
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:8
帖 子:36
专家分:178
注 册:2021-5-18
收藏
得分:10 
厉害,会用埃拉托斯特尼筛法生成素数表了。
疑惑,却不会区间素数的判断。
2021-09-14 11:46
qiansu
Rank: 1
等 级:新手上路
帖 子:7
专家分:0
注 册:2021-6-22
收藏
得分:0 
回复 5楼 diycai
啊 你这个内存超了 Memory Limit Exceeded
埃式法 这个模板是我很久以前找的
现在重新学了一遍 好多不清楚了

2021-09-14 12:26
快速回复:素数问题 c++
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.503643 second(s), 8 queries.
Copyright©2004-2021, BCCN.NET, All Rights Reserved