Amazon : find all primes less than n

find all primes less than n (出的个什么破题这是)

bool IsPrime(int a[], int num);

int InputPrime(int a[], int n)
{
        assert(a && n>0);
        if (1 == n) return 1;
        if (2 == n) return 2;

        a[0] = 1;
        a[1] = 2;
        int nRet = 2;

        for (int i = 3; i <= n; i++)
        {
                if (IsPrime(a, i))
                        a[nRet++] = i;
        }

        return nRet;
}

//Those none prime number has at least one prime factorial
bool IsPrime(int a[], int num)
{
        for (int i = 1; a[i]*a[i] < num; i++)
        {
                if (num%a[i] == 0)
                        return false;
        }

        return true;
}

用素数找素数，
在判断一个数是不是素数的时候可以判断它是否能整除被已经找到的素数，因为任何数字如果不是素数的话一定能分解成素数×某个数

Miller-Rabin test 简单又高效:

http://en.wikipedia.org/wiki/Miller-Rabin_test

Miller-Rabin test 简单又高效:
iveney 发表于 2011-6-23 01:17

    要说最简便的就是bitma, 一个32为int能包括的就6000多个prime

要说最简便的就是bitma, 一个32为int能包括的就6000多个prime
wwwyhx 发表于 2011-6-24 18:24

    what's bitma? bitmap? 建表算是 cheating 吧

直接删除比一个个的找要快,如果n比较小
memset(a,0, sizeof(a[0])*n);
a[0] = a[1] = 1;
for (int i = 2; i < n; ++i)
   if (!a[i]) {
      for (int j = 2; i * j < n; ++j) a[i*j] = 1;
}

for (int i = 2; i < n; ++i)
   if (!a[i]) cout <<i<<" ";

直接删除比一个个的找要快,如果n比较小
memset(a,0, sizeof(a[0])*n);
a[0] = a[1] = 1;
for (int i = 2; i < n; ++i)
   if (!a) {
      for (int j = 2; i * j < n; ++j) a = 1;
}

for (int i = 2; i < n; ++i)
   if (!a) cout
danielgao 发表于 2011-6-26 01:26

算是一个变通，不过条件就是n不能太大

用线性时间筛法可以在O(n)的时空复杂度内完成。

小的用筛，大的概率算法吧……再大再大就近似吧………………