#include <stdio.h>
#define N 1000000
char a[N];

int main(void)
{ 
    int prime[100000] = {0};
    int i,j, nPrime;

    nPrime = 0;

    for (i = 2; i < N; i++)
      a[i]= '1';

    for (i = 2; i < N; i++)
    { 
        if (a[i]) 
             prime[nPrime++] = i;

        for (j = 0; j < nPrime && i*(prime[j]) < N; j++) 
            a[i*prime[j]] = '\0';   
    }
     
    for (i = 2; i < N; i++)
    {
        if (a[i])
            printf("%d ", i);
    }
    printf("\n");
    
    return 0;
}

这种结论N年前我就知道了，怎么写这个函数相对高效的办法自己去看我写的电子书

混乱是指你自己的程序逻辑，多做了太明显的无用功

更新了吗？  

请问你是谁，你的电子书是什么?

难道是传说种的公众人物？？

求那个数是不是2为底的伪素数，基本上就可以筛掉99%以上的合数。如果求100以内的素数那么直接求伪素数就好了，第一个不是素数的2为底的伪素数出现在300以外。

对于一个数可以连续检验他是不是n个不同的数为底的伪素数，只要n取大于4的话那么如果他不是素数要过检验的概率基本就是0了；

[ 本帖最后由 zhddragon 于 2009-9-17 12:41 编辑 ]

#include <iostream>
using namespace std;

 
const int LIMIT = 1000000;

 
int main()
{
    bool sieve[LIMIT+1];
    int p, j, p2, i;

 
    int nLIMIT = LIMIT -6;
    for (i = 7 ; i <= nLIMIT ; i+=6)
    {
        sieve[i] = true;
        sieve[i+2] = false;
        sieve[i+4] = true;
    }

 
    p = 5;
    while ((j = p*p) <= LIMIT)
    {
        p2 = p << 1;
        while (j <= LIMIT)
        {
            sieve[j] = false;
            j += p2;
        }

 
        do
        {
            p += 2;
        } while (sieve[p] == false);
    }

 

 
    cout << "Prime numbers:\n";
    cout << "2,3,5";

 
    nLIMIT = LIMIT -4;
    for (i = 7 ; i <= nLIMIT ; i += 2)
    {
        if (sieve[i]) cout << "," << i ;
        i+=4;
        if (sieve[i]) cout << "," << i ;
    }

 
    return 0;
}

其实我不喜欢用辅助数组之类的


如果我要求的是一个大数大过size_t的范围。


又要考虑溢出。

这个好像是雨中飞燕妹妹(不知道对不对), 如果你想和她在算法上一较高下的话,你是找对人了.

就算i=4这种情况系统也不会出错，最后只是跳出这个for语句，去判断下个数是否是素数，完全对结果没有影响；举个法例给你:就算取等号时当i=3时也会出现2>i/2,系统照样执行。
再有，无论取不取等，我都试过结果都是一样的。

你哪里来的下一个数？？你在一楼的代码里只有这一行，我根本不知道你完整代码是怎么样
如果你说一样的话，麻烦你交出代码