[已解决]快速筛选素数

独一无②

在网上找一个快速筛选素数的方法，但是看不懂

若x≧1且n=6x-1或n=6x+1不是素数，那么n一定不是2和3的倍数。
证明：
∵n=6x-1或n=6x+1，即n=2(3x)-1或n=2(3x)+1或n=3(2x)-1或n=3(2x)+1。
∴n一定不是2和3的倍数。
将筛选法进行改进，只判断6x两侧的数。
原代码

1. #define N 100000000  
   
2. bool notPrime[N+5];  
   
3. void ScreeningPrime(void)  
   
4. {  
   
5.     int i, j, increment[6] = {0, 4, 0, 0, 0, 2};  
   
6.     for (i = 5; i*i <= N; i += increment[i%6])  
   
7.     {  
   
8.         for (j = i; i*j <= N; j += increment[j%6])  
   
9.         {  
   
10.             notPrime[i*j] = true;  
    
11.         }
    
12.     }
    
13. }

复制代码

谁可以给我解释解释，看不懂，并且我直套用也不行

1. # include<iostream>
   
2. #define N 100000000  
   
3. bool notPrime[N+5];  
   
4. int main()  
   
5. {  
   
6.     int i, j, increment[6] = {0, 4, 0, 0, 0, 2};  
   
7.     for (i = 5; i*i <= N; i += increment[i%6])  
   
8.     {  
   
9.        for (j = i; i*j <= N; j += increment[j%6])  
   
10.        {  
    
11.            notPrime[i*j] = true;  
    
12.        }  
    
13.     }  
    
14.     for(i=5;i<=100;i++)  //好像根本没有筛选，都输出了
    
15.     {
    
16.                   if(!notPrime[i])
    
17.                   printf("%d\n",i);
    
18.            }
    
19. }

复制代码

最佳答案

月排行榜 / 总排行榜

人造人

2016-1-13 18:01:54

1. #include <stdio.h>
   
2. 
   
3. #define N 1000
   
4. 
   
5. int yesPrime[N];
   
6. 
   
7. void ScreeningPrime();
   
8. 
   
9. int main()
   
10. {
    
11.         int i;
    
12. 
    
13.         ScreeningPrime();
    
14. 
    
15.         for (i = 5; i < 100; i++)
    
16.         {
    
17. 
    
18.                 printf("%d is :%d\n", i, yesPrime[i]);
    
19.         }
    
20. 
    
21.         return 0;
    
22. }
    
23. 
    
24. void ScreeningPrime(void)
    
25. {
    
26.         int i, increment[6] = { 0, 4, 0, 0, 0, 2 };
    
27.         for (i = 5; i < N; i += increment[i % 6])
    
28.         {
    
29.                         yesPrime[i] = 1;
    
30.         }
    
31. }

复制代码

我改了一下，
你看下能不能看懂

注：算法有问题，有一些不是素数的也混进来了
25 能混进来是因为 5 没有算进去
49 能混进来是为什么？

跳转到最佳答案楼层

人造人

1. #include <stdio.h>
   
2. 
   
3. #define N 1000
   
4. 
   
5. int yesPrime[N];
   
6. 
   
7. void ScreeningPrime();
   
8. 
   
9. int main()
   
10. {
    
11.         int i;
    
12. 
    
13.         ScreeningPrime();
    
14. 
    
15.         for (i = 5; i < 100; i++)
    
16.         {
    
17. 
    
18.                 printf("%d is :%d\n", i, yesPrime[i]);
    
19.         }
    
20. 
    
21.         return 0;
    
22. }
    
23. 
    
24. void ScreeningPrime(void)
    
25. {
    
26.         int i, increment[6] = { 0, 4, 0, 0, 0, 2 };
    
27.         for (i = 5; i < N; i += increment[i % 6])
    
28.         {
    
29.                         yesPrime[i] = 1;
    
30.         }
    
31. }

复制代码

我改了一下，
你看下能不能看懂

注：算法有问题，有一些不是素数的也混进来了
25 能混进来是因为 5 没有算进去
49 能混进来是为什么？

人造人

这个程序真的是筛选素数吗？
我看不像啊

你要直接套用也应该这样吧


#include <stdio.h>

#define N 100000000  
bool notPrime[N + 5]; //bool 类型 ，在c++环境中编译（后缀为.cpp）

void ScreeningPrime(void);

int main()
{
        int i;

        ScreeningPrime ();

        for (i = 5; i <= 100; i++)
        {

                printf("%d\n", notPrime[i]); //程序应该是在函数 ScreeningPrime中赋值notPrime数组，在这里输出
        }
}

void ScreeningPrime(void)
{
        int i, j, increment[6] = { 0, 4, 0, 0, 0, 2 };

        for (i = 5; i*i <= N; i += increment[i % 6])  // 为什么i 要加 increment中的某个元素
        {
                for (j = i; i*j <= N; j += increment[j % 6])
                {
                        notPrime[i*j] = true; // 为什么把i * j 的地方赋值为true
                }
        }
}

你在哪找到的这个程序

人造人

人造人 发表于 2016-1-13 21:59
这个程序真的是筛选素数吗？
我看不像啊

这个字体怎么是斜的

独一无②

人造人 发表于 2016-1-13 22:01
这个字体怎么是斜的

http://blog.csdn.net/code_pang/article/details/8022302

我是在上面 那个连接 看到的，里面有两个代码，上面那个看懂了，下面这个不懂，于是就发帖问了

人造人

独一无② 发表于 2016-1-13 22:07
http://blog.csdn.net/code_pang/article/details/8022302

我是在上面 那个连接 看到的，里面有两个代 ...

刚刚看那个题时发现一个问题

∵n=6x-1或n=6x+1，即n=2(3x)-1或n=2(3x)+1或n=3(2x)-1或n=3(2x)+1。
∴n一定不是2和3的倍数。
不是2和3的倍数就是素数吗？
当x = 4 时
n = 25
25 不是素数吧

SXTDU

人造人 发表于 2016-1-13 23:40
我改了一下，
你看下能不能看懂

是你理解错了 只是说素数一定位于6x两侧 并没说6x两侧一定是素数

独一无②

人造人 发表于 2016-1-13 23:40
我改了一下，
你看下能不能看懂

他的 那个筛选素数 好像 是有2个for 循环构成的，但是我试了一下，好像也不行

SXTDU

独一无② 发表于 2016-1-14 11:39
他的 那个筛选素数 好像 是有2个for 循环构成的，但是我试了一下，好像也不行

http://m.blog.csdn.net/article/details?id=7880245这个更好 你找的这个他没写完整

人造人

SXTDU 发表于 2016-1-14 11:23
是你理解错了 只是说素数一定位于6x两侧 并没说6x两侧一定是素数

哦，谢谢

littlestar

用线性筛吧