精华内容
下载资源
问答
  • 筛选法求素数c++
    2022-04-14 22:26:18

    筛选法求素数

    输入m、n(m,n<100),输出[m,n]之间的素数。要求:使用筛选法求素数。

    求100以内素数的筛选过程:在一张纸上写上1到100全部整数,然后逐个判断它们是否是素数, 找出所有的非素数,把它挖掉,最后剩下的就是素数。提示:可以将1100这些数存储于数组1100下标,挖掉的数据置为0。

    具体做法如下:

    <1> 先将1挖掉(因为1不是素数)。

    <2> 找到数组中第一个非零值(2),把2的倍数挖掉。

    <3> 重复步骤<2>,再把3,。。。的倍数挖掉,直至11时结束(实际上可以挖掉7的倍数后即可结束)。

    <4> 数组中非零值即为素数。

    Sample Input

    5 19

    Sample Output

    5 7 11 13 17 19

    #include<iostream>

    using namespace std;

    const int Max = 101;

    int main()

    {

        int a[Max], i, j,m,n;

           for (i = 1; i < 101; i++)//可以将1~100这些数存储于数组1~100下标

                  a[i] = i;

           a[1] = 0;//挖掉的数据置为0

           for (j = 2; j <= 11;j++)

                  for (i = j + 1; i < 101; i++)//遍历数组将符合条件的置为0

                         if (a[i] % j == 0)

                                a[i] = 0;

           cin >> m >> n;

           for (i = m; i <= n; i++)

                  if (a[i] != 0)//数组中非零值即为素数

                         cout << a[i] << " ";

           cout << endl;

           return 0;

    }

    更多相关内容
  • 筛选法求素数-c++

    2021-04-02 20:27:33
    筛选法求n以内的素数筛选法求解过程为:将2~n之间的正整数放在数组内存储,将数组中2之后的所有能被2整除的数清0,再将3之后的所有能被3整除的数清0 ,以此类推,直到n为止。数组中不为0 的数即为素数。 输入...

    筛选法的应用—求素数

    题目描述
    用筛选法求n以内的素数。筛选法求解过程为:将2~n之间的正整数放在数组内存储,将数组中2之后的所有能被2整除的数清0,再将3之后的所有能被3整除的数清0 ,以此类推,直到n为止。数组中不为0 的数即为素数。
    输入描述:
    多组输入,每行输入一个正整数(不大于100)。
    输出描述:
    针对每行输入的整数n,输出两行,第一行,输出n之内(包括n)的素数,用空格分隔,

    第二行,输出数组中2之后0 的个数。每行输出后换行。
    示例1
    输入

    20
    

    输出

    2 3 5 7 11 13 17 19
    11
    

    解:

    #include<iostream>
    
    using namespace std;
    
    int main ()
    {
        int n,result=0;
        int num[100];
        while(cin>>n)
        {
             for(int i=2;i<=n;i++)  //将2~n之间的正整数放入数组
             {
                 num[i]=i;    //给数组赋值 
             }
             
            for(int i=2;i<=n;i++)  //遍历数组
            {
                for(int j=i+1;j<=n;j++)   //将数组中2之后的所有能被2整除的数清0,
    									//再将3之后的所有能被3整除的数清0
    									//以此类推,直到n为止。数组中不为0 的数即为素数
                
    			if(num[j]%i==0)   //被n整除即%n==0!!!!!
                {
                    num[j]=0;
                }
            }
            for(int i=2;i<=n;i++)
            {
                if(num[i]!=0)
                    cout<<num[i]<<" ";
                else
                {
    			result++;      //输出2之后的零的数
    			}
            }
            cout<<endl;
            cout<<result<<endl;
        }
    }
    
    展开全文
  • 筛选法又称筛法,是不超过自然数N(N>1)的所有质数的一种方法。据说是古希腊的埃拉托斯特尼(Eratosthenes,约公元前274~194年)发明的,又称埃拉托斯特尼筛子。 具体做法是: 先把N个自然数按次序排列起来。1...
  • C++法求素数

    千次阅读 2021-10-21 16:58:31
    一般方法 #include<iostream> #include<cmath> //用sqrt()这个函数需要加的头文件 using namespace std; int prime(int n) { for(int i=2;i<sqrt(n);i++) //不需要到n,到根号n就已经足够 {...

    假定题目为输出n以内的所有素数

    一般方法 

    最容易理解的一个方法,从0遍历到根号n判断n是否能被整除。使用时只需要记住判断到根号n就可以了。

    但是时间复杂度是o(n*sqrt(n)),效率略低。

    代码如下:

    #include<iostream>
    #include<cmath>			//用sqrt()这个函数需要加的头文件 
    using namespace std;
    int prime(int n)
    {
    	for(int i=2;i<sqrt(n);i++)		//不需要到n,到根号n就已经足够 
    	{
    		if(n%i==0)	return 0;		//不是素数返回0,是素数返回1 
    	}
    	return 1;
    }
    int main()
    {
    	int n;
    	cin>>n;
    	
    	for(int i=1;i<=n;i++)
    	if(prime(i))	cout<<i<<" ";	//如果是素数就打印在屏幕上 
    	
    	return 0;
    } 

    普通筛——埃拉托斯特尼(Eratosthenes)筛法

    基本思路:

    定义一个长度为maxn的布尔变量数组prime[maxn],数组元素为0则代表所对应的下标为素数,数组元素为1则代表所对应的下标为合数。(下文中2代表prime[2],2的值为prime[2]的值)

    我们先把数组里所有元素的值设为1,代表着目前所有小于n的数都被认为是素数。

    假设有一个指针,当他指向2时,2的值为1,表示2为素数,程序把2的倍数4,6,8等的值全部设置成0,这代表他们不被认为是素数。

    然后那个指针指向3,3的值为1,表示3为素数,程序把3的倍数6,9,12等的值全部设置成0,这代表他们也不被认为是素数。

    指针指向了4,4的值已经被指针指向2时设置成了0。它不是素数,没有必要把它的倍数的值也设置成0,因为4能筛掉的合数,2也都能筛掉。

    然后就是指针不断的向后移动,找到素数的值,把它们的倍数的值全部设置成0,直到筛到根号n

    因为这种算法是层层筛选素数,所以叫筛法求素数。

    函数体代码如下:

    const int maxn=10000;						//具体的maxn看题目要求 
    bool prime[maxn];
    void judge_prime(int n)
    {
    	memset(prime,1,sizeof(prime));			//把prime数组全部初始化为1 
    	for(int i=2;i<n;i++)					//for循环可以实现上面所说的指针的功能 
    	{
    		if(prime[i]==1)						//找到素数 
    		for(int j=i*2;j<=n;j+=i)			//把n以及n以内i的倍数的值全部设为0 
    		{
    			prime[j]=0;
    		}
    	}	
    }

    memset(a,b,c)将a这个地址之后c个字节的值全部替换为b

    sizeof(a),返回a总共所占的字节数

    第一个循环来找素数,第二个循环来枚举那个素数的倍数

    上面讲到的这种方法其实有优化的空间,j刚开始不需要设为2i,可以优化为i*i,指针也和基础方法一样,不用指到n,只需要指到根号n(我也不知道为什么,问数学家去)

    优化前的时间复杂度有o(nloglogn),优化后就大概接近o(n)了

    优化后的总体代码如下:

    #include<iostream>
    #include<cmath>
    #include<string.h>							//包含memset的头文件,也可以写成cstring 
    using namespace std;
    const int maxn=10000;						//具体的maxn看题目要求 
    bool prime[maxn];
    void judge_prime(int n)
    {
    	memset(prime,1,sizeof(prime));			//把prime数组全部初始化为1 
    	prime[0]=0;prime[1]=0;					//加上这两句显得更严谨( 
    	for(int i=2;i<n;i++)					//for循环可以实现上面所说的指针的功能 
    	{
    		if(prime[i]==1)						//找到素数 
    		for(int j=i*2;j<=n;j+=i)			//把n以及n以内i的倍数的值全部设为0 
    		{
    			prime[j]=0;
    		}
    	}	
    }
    int main()
    {
    	int n;
    	cin>>n;
    	judge_prime(n);
    	for(int i=0;i<=n;i++)
    	{
    		if(prime[i])						//如果prime[i]=1,也就是i被认为是素数时,输出i 
    		cout<<i<<" ";	
    	} 
    	return 0;
    } 

    线性筛——欧拉Euler筛

    基本思路:

    你有没有注意到,埃氏筛法在指针指向2和3时都把6的值设为了0,重复了,所以会有些浪费,终究不能达到o(n)的时间复杂度。

    通过离散数学中的知识,我们可以知道每个合数都能分割成一个素数a和另一个数i(可以是素数)的乘积。

    那么欧拉筛要做的,就是要保证每个合数只会被分割后的最小素数a筛掉,避免重复。

    先放代码,方便理解:

    const int maxn=1e7;
    bool prime[maxn+5];
    int sto_prime[maxn+5];
    void judge_prime(int n)
    {
    	int cot=0;
    	memset(prime,1,sizeof(prime));
    	prime[0]=0;prime[1]=0;
    	for(int i=2;i<n;i++)							//外层循环指向不同的数i 
    	{
    		if(prime[i])	sto_prime[cot++]=i;			//保存素数到int数组里 
    		for(int j=0;j<cot;j++)						//内层循环指向不同的素数 
    		{
    			if(i*sto_prime[j]>n)	break;			//如果要筛的那个数超出了最大值,退出内层循环 
    			prime[i*sto_prime[j]]=0;				//筛数 
    			if(i%sto_prime[j]==0)	break;			//最重要的一句, 保证只每个合数只筛一次 
    		}
    	}	
    }

    具体到实现上,我们除了要像上面一样定义一个bool类型的数组,还要定义一个int类型的数组,专门用来存放筛选出来的素数。

    还需要两层循环来枚举素数sto_prime和另一个数i。

    内层从小到大枚举 sto_prime[j]。i×sto_rime[j] 是尝试筛掉的某个合数,其中,我们期望 sto_rime[j] 是这个合数的最小质因数 (这是线性复杂度的条件,下面叫做“筛条件”)。它是怎么得到保证的?

    j 的循环中,有一句就做到了这一点:

    if(i%sto_prime[j]==0)	break;

    j 循环到 哪里 就恰好需要停止的理由是:

    • 下面用 s(smaller)表示小于 j 的数,l(larger)表示大于 j 的数。

    • ① i 的最小质因数肯定是 sto_prime[j]。

      (如果 i 的最小质因数是 sto_prime[s] ,那么 sto_prime[s] 更早被枚举到(因为我们从小到大枚举质数),当时就要break)

      既然 i 的最小质因数是 sto_prime[j],那么 i × sto_prime[j] 的最小质因数也是 sto_prime[j]。所以,j 本身是符合“筛条件”的。

    • ② i × sto_prime[s] 的最小质因数确实是 sto_prime[s]。

      (如果是它的最小质因数是更小的质数 sto_prime[s],那么当然 sto_prime[s] 更早被枚举到,当时就要break)

      这说明到 j 之前(用 i × sto_prime[s] 的方式去筛合数,使用的是最小质因数)都符合“筛条件”。

    • ③ i × sto_prime[l] 的最小质因数一定是 sto_prime[l]。

      (因为 i 的最小质因数是 sto_prime[j],所以 i × sto_prime[l]也含有 sto_prime[j] 这个因数(这是因为),所以其最小质因数也是 sto_prime[j](新的质因数 sto_prime[l] 太大了))

      这说明,如果 j 继续递增(将以 i × sto_prime[l] 的方式去筛合数,没有使用最小质因数),是不符合“筛条件”的。

    欧拉筛因为每个数都只被筛一次,复杂度只有o(n),是最好的筛选素数的方法。

    展开全文
  • 详解埃氏筛选法筛选素数C++实现)

    千次阅读 多人点赞 2019-03-24 15:42:32
    当范围在int范围内: #include&lt;iostream&gt; #include&lt;cstdio&gt;...using namespace std;... // 存储一个个确定为质数的数 bool is_prime[maxn+1]; // 标记范围内所有数 int p = 0; int ...

    说明:篇中的nN都是同一个意义,大小写不过是为了表现具体和一般形式而已,穿插着用可能让读者容易混淆,请多体谅。

    一、质数定义

    指在大于1的整数中,只能被1和它本身整除的数。

    二、埃氏筛选法最重要的结论:

    N有因数的话,那么至少有一半的因数不会超过 N \sqrt{N} N
    举个例子,要判断100是不是质数,100 = 10 X 10,只要有1个因数 > 100 \sqrt{100} 100 ,必然另1个因数 < 100 \sqrt{100} 100 ,这样只要判断10以内有无100的因数即可,使用这种方法的时间复杂度为O(n*√n)。
    可能这样你还不是很懂,继续往下看。

    三、找到[0,n]范围内所有素数 的算法基本思路

    1. 首先将0、1排除:

    2. 创建从2到n的连续整数列表,[2,3,4,…,n];

    3. 初始化 p = 2,因为2是最小的质数;

    4. 枚举所有p的倍数(2p,3p,4p,…),标记为非质数(合数);

    5. 找到下一个 没有标记 且 大于p 的数。如果没有,结束运算;如果有,将该值赋予p,重复步骤4;

    6. 运算结束后,剩下所有未标记的数都是找到的质数。

    可以结合下面这张动图理解:
    在这里插入图片描述

    四、应用埃氏筛选法优化后的思路

    我们发现 [0, N] 范围内很多 > N \sqrt{N} N 的数其实是[0, N \sqrt{N} N ]范围内数的倍数。而 > N \sqrt{N} N 且 非[0, N \sqrt{N} N ]范围内数字的倍数的,都是质数。
    举个例子: [0, 100] 范围内很多 > 100 \sqrt{100} 100 的数其实是[0, 100 \sqrt{100} 100 ]范围内数的倍数(12,14,16是2的倍数,12,15,18是3的倍数…)。而 > 100 \sqrt{100} 100 且 非[0, 100 \sqrt{100} 100 ]范围内数字的倍数的(11,13,17…),都是质数。

    所以对 标题三 的基本算法思路做出如下优化:
    对于步骤4,可以不用从2p开始排除,而是直接从 p 2 p^2 p2 开始。理由已经在开始讲过,所有的小于 p 2 p^2 p2 的合数都有更小的因数而被排除。

    对于步骤5,当 p 2 p^2 p2 > n 的时候停止计算。


    参考链接:
    《使用埃拉托色尼筛选法在21亿内快速查找质数》
    《埃拉托色尼筛选法巧解质数问题》


    当范围在int范围内:

    #include<iostream>
    #include<cstdio>
    using namespace std;
        
    const int maxn=5000000;
    long prime[maxn];    // 存储一个个确定为质数的数
    bool is_prime[maxn+1];    // 标记范围内所有数
    int p = 0;
    int sieve(int n)
    {
     	p = 0;
    	for(int i=0;i<=n;i++)
    		is_prime[i]=true;       // 所有数先标记为true
        is_prime[0] = is_prime[1] = false;   // 把数字0,1标记为质数
        for(int i=2;i<=n;i++)
        {
           	if(is_prime[i])         // 如果这个数没有被标记为false
        	{
                 prime[p++]=i;       // 用prime数组存起来这个数,既存起了质数,又用p表示了质数个数
                 for(int j=i*i;j<=n;j+=i)   // 这里没有优化时的写法是for(int j=2*i; j<=n; j++)。
    	    	//因为小于j(即i^2)内的合数都因为(根号j)(即i)内有更小的j的的因数而被排除
        							// 比如3^2 = 9,为什么不算2*3 = 6呢, 因为6<9,所以6因为3以内有更小的因数而直接被排除
        				is_prime[j]=false;
            }
        }
        return p;          // 返回质数个数
    }
    int main()
    {
    	int n;
    	while(~scanf("%d",&n))
        {
        	printf("质数个数是: %d\n",sieve(n));
        	printf("质数有:\n");
        	for (int i = 0; i<p; i++)
        	{
        		printf("%d ", prime[i]);
        		printf("\n\n");
            }
       	}
        system("pause");
    }	
    

    当范围超过了int

    static const int N = 1e7;
    bool is_prime[N];   // 判断是否是素数
    ll prime[N];       // 存储素数
    ll sieve(ll num)
    {
    	int inx = 0;
    	for (int i = 0; i<=N; i++)
    		is_prime[i] = true;
    
    	is_prime[0] = is_prime[1] = false;
    
    	int MIN = (num > N) ? N : num;
    
    	for (ll i = 2; i<=MIN; i++)
    	{
    		if (is_prime[i])
    		{
    			prime[inx++] = i;
    
    			for (ll j = i*i; j<=num; j+=i)
    				is_prime[j] = false;
    		}
    	}
    	return inx;
    }
    
    int gcd(int inx)    // 此处由于传进来都是质数,所以直接相乘即为gcd
    {
    	int res = 1;
    	for (int i = 0; i<inx-1; i++)
    		res *= prime[i];
    	return res;
    }
    
    void C3()
    {
    	ll num;     // 输入数
    	int p;       // 最小公约数
    
    	cin >> num;
    
    	int inx = sieve(num);   // 筛选素数
    
    	cout << gcd(inx) << endl;
    }
    
    展开全文
  • 筛选法求素数

    2012-10-09 12:59:12
    C++为编程语言,筛选法,编写的一个数以内的素数
  • C++筛选法求素数(简单)

    千次阅读 2018-03-16 11:34:13
    筛选法求素数经常是求解其他问题的前提 代码: #include &lt;bits/stdc++.h&gt; using namespace std; const int N = 100001; int prime[N]{0}; int main() { for(int i=2;i!=N;++i) prime[i] = 1; ...
  • 求素数(依题限制多种解法)(C++) 题目 从键盘上输入一个正整数N(N<=100),N之内的素数 样例输入复制 100 样例输出复制 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 解法 素数...
  • c++素数筛选法

    2020-08-30 09:32:09
    本文讲的是筛选法C++实现, 筛选法又称筛法,是不超过自然数N(N>1)的所有质数的一种方法。据说是古希腊的埃拉托斯特尼(Eratosthenes,约公元前274~194年)发明的,又称埃拉托斯特尼筛子。
  • 筛选法求素数模板

    2018-07-22 18:24:36
    #include&lt;iostream&gt; #include&lt;cmath&gt;...using namespace std;...///要求的素数的范围  bool flag[10000];  int m=sqrt(a+0.5);  for(int i=2;i&lt;=m;i++)  if(!flag...
  • c++求素数筛选法

    千次阅读 2019-03-28 18:47:45
    #include<iostream> #include<math.h> using namespace std; const int N = 100; bool prime[N]; //布尔数组变量0、1 //得到N以内的素数 void primeNum...
  • [数值问题]素数筛选 内存限制:128 MB时间限制:1.000 S 题目描述 输入一正整数n(2<=n<=5*10^6),按顺序输出2到n范围内的所有素数。 输入 输入共一行一个数,表示n的值。 输出 输出若干行,每行5个...
  • 发现我们对于同一个数的计算方式不同。那么怎样才能确定一个唯一的计算方式呢?关键是找质因子,因为每一个大于1的正整数都能分解为若干个质数的乘积
  • 素数筛选法 定义数组用来表示是否为素数:1为素数,2不为素数,开始全部初始化为1 将2的倍数全部设置为非素数 再将3,4,5…的倍数设置为非素数 这样将整个数组中的数的素数设置为1,非素数设置为0 ...
  • C++: 筛选法查找素数/质数

    千次阅读 2020-05-29 11:58:27
    本题要求使用筛法求出1~N以内的质数。 //函数接口定义: vector<int> sieve(int n); //函数声明, n以内的质数~ 题目要求:n以内的质数。其中 n是传入的参数。n 的值不超过10 000 000的范围; 出的质数存入容器...
  • 筛选法求素数&一般方法求素数&判断一个数是否是素数 1.判断一个数是否是素数 #include<stdio.h> #include<math.h> int main() { int n, i, k; printf("please enter a integer number");...
  • 埃式筛选法求素数

    2017-12-26 11:18:00
    //是素数倍数数不是素数 } } } return p; } int main() { int n; scanf( " %d " ,& n); printf( " %d " ,sieve(n)); return 0 ; }   转载于:...
  • 要枚举n以内的素数,可以用埃氏筛。这是一个与辗转相除一样古老的算法。 首先,将2到n范围内的所有整数写下来。其中最小的数字2是素数。将表中所有2的倍数都划去。表中剩余的最小数字是3,它不能被更小的数...
  • Bitset是C++语言的一个类库,用来方便地管理一系列的bit位而不用程序员自己来写代码,C++的 bitset 在 bitset 头文件中,它是一种类似数组的结构,它的每一个元素只能是0或1,每个元素仅用1bit空间。 #include &...
  • 谭浩强C++课后习题14——筛选法求素数 题目描述:用筛选法求100之内的素数。 算法思路:所谓筛选法是指把非素数挖掉,剩下的就是素数。这里用一个数组令所有初始值为1,为了方便第一个数num[0]不用,先把1挖掉(让其...
  • 原理:素数,指在一个大于1的自然数...一个比较常见的求素数的办法是埃拉托斯特尼筛(the Sieve of Eratosthenes),说简单一点就是画表格,然后删表格,如图所示:从2开始依次往后面数,如果当前数字一个素数,那么...
  • 筛选法指的是“埃拉托色尼(Eratosthenes)筛选法”。他是古希腊著名数学家。他采取的方法是:在一张纸上写上1~1000全部整数,然后逐个判断他们是否为素数,找出一个非素数就把他挖掉。最后剩下的就是素数。 具体...
  • 法求N以内的素数 C++

    千次阅读 2019-03-10 17:09:56
    法求n以内的素数法求素数:把2到n中所有的数都列出来,然后从2开始,先划掉n内所有2的倍数,然后每次从下一个剩下的数(必然是素数)开始,划掉其n内的所有倍数。最后剩下的数,就都是素数。 是以空间换...
  • j筛选法求素数

    2012-12-29 08:26:00
    筛选法求素数,在大范围内求素数比其他方法高效很多。
  • C++求素数方法

    2021-11-06 17:12:25
    方法二:筛选法求素数 错误一:对筛选法的含义不清 筛选法:即通过将含有2、3、……因子的数字筛选出去来找素数。 此时,找素数的两重循环位置改变。 遍历素数法:大循环是个个数字,小循环是因子。 筛选法求...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,494
精华内容 997
关键字:

筛选法求素数c++

c++ 订阅