素数

第一种

效率一般的：

输入50000计算出结果耗时4.033s

#include <iostream>
using namespace std;

int main()
{
    int n;
    cin >> n;
    cout << 2 <<endl;
    for(int i=3; i<=n; i++)
    {
        int j;
        for(j=3; j<i; j++)
        {
            if(i % j == 0)
                break;
        }
        if(j == i)
            cout << i <<endl;
    }
    return 0;
}
  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
 

第二种

略去了偶数的判断，并且只进行到根号下次

50000耗时3.018s

#include <iostream>
#include <cstdio>
using namespace std;

int main()
{
    int n;
    cin >> n;
    cout << 2 << endl;
    for(int i=3; i<=n; i+=2)//偶数直接跳过不加判断
    {
        int j;
        for( j=3; j<i; j+=2)//同样奇数的因子不可能是偶数，跳过
        {
            if(i % j== 0)//存在因子就结束
                break;
            if(j * j > i)//超过根号下次就结束
                break;
        }
        if(j * j > i)//说明是第二个break掉的，说明不存在因子！
            cout << i <<endl;
    }
    return 0;
}
  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
 

筛法求素数：

利用的是数组，空间换时间加快计算速度

#include <iostream>
using namespace std;

#define MAX 5000
char isprime[MAX + 10];
int main()
{
    for(int i=2; i<=MAX; i++)
        isprime[i] = 1;
    for(int i=2; i<= MAX; i++)
    {
        if( isprime[i])
            for(int j=i*2; j<= MAX; j+=2)
                isprime[j] = 0;
    }
    for(int i=2; i<MAX; i++)
    {
        if(isprime[i])
            cout<< i << endl;
    }
    return 0;
}
  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
 

文章来源: recclay.blog.csdn.net，作者：ReCclay，版权归原作者所有，如需转载，请联系作者。

原文链接：recclay.blog.csdn.net/article/details/60334374