5.2 筛法求素数

今天药忘吃喽~ 2022-05-20 07:18 187阅读 0赞

![70][]![70 1][]![70 2][]![70 3][]

一个数，如果只有1和它本身两个[因数][Link 1]，这样的数叫质数（或素数）。如2、3、5、7都是质数。  
一个数，如果除了1和它本身还有别的因数，这样的数叫[合数][Link 2]。如4、6、15、49都是合数。  
1既不是质数，也不是合数。

#include<iostream>
    #include<cstdio>
    using namespace std;
    int main()
    {
    	int n;
    	cin >> n;
    	cout << 2 << endl;
    	for(int i = 3; i <= n; i += 2)//i += 2删除偶数的情况 
    	{
    		int j;
    		for(j = 3; j < i; j += 2)//j += 2 奇数的因子不可能为偶数，为奇数 
    		{
    			if(i % j == 0) break;
    			if(j * j > i) break;//j大于i的平方根后，另一个因子肯定小于i的平方根，已经计算过了	
    		}
    		if(j * j > i) 
    			cout << i << endl;
    	}
    	return 0;
    }

#include<iostream>
    #include<cstdio>
    #include<cmath>
    using namespace std;
    int main()
    {
    	int n;
    	cin >> n;
    	cout << 2 << endl;
    	for(int i = 3; i <= n; i += 2)//i += 2删除偶数的情况 
    	{
    		int j;
    		for(j = 3; j < sqrt(i); j += 2)//j += 2 奇数的因子不可能为偶数，为奇数 
    		{
    			if(i % j == 0) break;
    		}
    		if(j > sqrt(i))
    			cout << i << endl;
    	}
    	return 0;
    }

[循环案例选讲（阶乘、质数）][Link 3]

![70 4][]

![70 5][]

[整型在字符数组中的存储][Link 4]

其实整型在字符数组中的存储，就是将值转化成ASCII值进行存储，类似于哈希表的方式，一个键对应一个值，
    
    我们只需要找到它的键，进而取出它的值即可使用。
    
    所以我们不用担心整型存储到字符数组中会变成字符型，因为我们存储的是整型所对应的ASCII值，而不是整型本身。

#include<iostream>
    #define MAXN 10000000
    using namespace std;
    char isprime[MAXN+10];//不用int型，int类型占用4个字节,char占用1个字节。
    //MAXN至少+1，数组下标是从0开始的，所以如果不+1，最大为a[MAXN-1] 
    int main()
    {
    	int n;
    	cin >> n;
    	for(int i = 2; i <= n; ++i)
    		isprime[i] = 1;//1表示isprime[i]为素数
    	for(int i = 2; i <= n; ++i)
    	{
    		if(isprime[i])//判断如果已经是合数就不必再计算了 
    		{
    			for(int j = 2 * i; j <= MAXN; j += i)//注意为j+=i，表示增加i步长即每次增加一倍 
    			{
    				isprime[j] = 0;//倍数即为合数 
    			}
    		}
    	} 
    	for(int i = 2; i <= n; ++i)
    	{
    		if(isprime[i])
    		{
    			cout << i << endl;
    		}
    	} 
    	return 0;	 
    }

[70]: https://img-blog.csdn.net/20180714172133702?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbnlhbndlbm1lbmc=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[70 1]: https://img-blog.csdn.net/20180714172147123?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbnlhbndlbm1lbmc=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[70 2]: https://img-blog.csdn.net/20180714172157378?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbnlhbndlbm1lbmc=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[70 3]: /images/20220520/a11d341f28f545a0a88bba518a90a79b.png
[Link 1]: http://www.so.com/s?q=%E5%9B%A0%E6%95%B0&ie=utf-8&src=internal_wenda_recommend_textn
[Link 2]: http://www.so.com/s?q=%E5%90%88%E6%95%B0&ie=utf-8&src=internal_wenda_recommend_textn
[Link 3]: https://blog.csdn.net/yanyanwenmeng/article/details/81029373
[70 4]: /images/20220520/b315835bdff546acabd55ead27b68cf6.png
[70 5]: /images/20220520/7864a69d05444ea6b3e3f70072066cbf.png
[Link 4]: https://blog.csdn.net/Xzg_2017/article/details/80098838