独一无② 发表于 2016-1-13 18:01:53

快速筛选素数

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

若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;
void ScreeningPrime(void)
{
    int i, j, increment = {0, 4, 0, 0, 0, 2};
    for (i = 5; i*i <= N; i += increment)
    {
      for (j = i; i*j <= N; j += increment)
      {
            notPrime = true;
      }
    }
}

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

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

人造人 发表于 2016-1-13 18:01:54

#include <stdio.h>

#define N 1000

int yesPrime;

void ScreeningPrime();

int main()
{
        int i;

        ScreeningPrime();

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

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

        return 0;
}

void ScreeningPrime(void)
{
        int i, increment = { 0, 4, 0, 0, 0, 2 };
        for (i = 5; i < N; i += increment)
        {
                        yesPrime = 1;
        }
}
我改了一下，
你看下能不能看懂

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

人造人 发表于 2016-1-13 21:59:58

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

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


#include <stdio.h>

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

void ScreeningPrime(void);

int main()
{
        int i;

        ScreeningPrime ();

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

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

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

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

你在哪找到的这个程序

人造人 发表于 2016-1-13 22:01:38

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



这个字体怎么是斜的

独一无② 发表于 2016-1-13 22:07:24

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

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

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

人造人 发表于 2016-1-13 23:09:23

独一无② 发表于 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-14 11:23:53

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



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

独一无② 发表于 2016-1-14 11:39:52

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



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

SXTDU 发表于 2016-1-14 12:10:18

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

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

人造人 发表于 2016-1-14 13:00:08

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

哦，谢谢

littlestar 发表于 2016-2-1 16:46:48

用线性筛吧
页: [1]
查看完整版本: 快速筛选素数