[已解决]快速筛选素数

独一无②

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

若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两侧的数。
原代码

#define N 100000000  
bool notPrime[N+5];  
void ScreeningPrime(void)  
{  
    int i, j, increment[6] = {0, 4, 0, 0, 0, 2};  
    for (i = 5; i*i <= N; i += increment[i%6])  
    {  
        for (j = i; i*j <= N; j += increment[j%6])  
        {  
            notPrime[i*j] = true;  
        } 
    }
}

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

# include<iostream> 
#define N 100000000  
bool notPrime[N+5];  
int main()  
{  
    int i, j, increment[6] = {0, 4, 0, 0, 0, 2};  
    for (i = 5; i*i <= N; i += increment[i%6])  
    {  
       for (j = i; i*j <= N; j += increment[j%6])  
       {  
           notPrime[i*j] = true;  
       }  
    }  
    for(i=5;i<=100;i++)  //好像根本没有筛选，都输出了 
    {
                  if(!notPrime[i])
                  printf("%d\n",i);
           }
} 

最佳答案

月排行榜 / 总排行榜

人造人

2016-1-13 18:01:54

#include <stdio.h>

#define N 1000

int yesPrime[N];

void ScreeningPrime();

int main()
{
        int i;

        ScreeningPrime();

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

                printf("%d is :%d\n", i, yesPrime[i]);
        }

        return 0;
}

void ScreeningPrime(void)
{
        int i, increment[6] = { 0, 4, 0, 0, 0, 2 };
        for (i = 5; i < N; i += increment[i % 6])
        {
                        yesPrime[i] = 1;
        }
}

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

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

跳转到最佳答案楼层

人造人

#include <stdio.h>

#define N 1000

int yesPrime[N];

void ScreeningPrime();

int main()
{
        int i;

        ScreeningPrime();

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

                printf("%d is :%d\n", i, yesPrime[i]);
        }

        return 0;
}

void ScreeningPrime(void)
{
        int i, increment[6] = { 0, 4, 0, 0, 0, 2 };
        for (i = 5; i < N; i += increment[i % 6])
        {
                        yesPrime[i] = 1;
        }
}

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

注：算法有问题，有一些不是素数的也混进来了
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

用线性筛吧