素数判断

OJ_算法

素数判断方法：

　问题：求出所有小于等于n的素数

方法1：

原理：一个数 n 如果是合数，那么它的所有的因子不超过sqrt(n)--n的开方；
方案：使用循环解决；
时间复杂度：o(n*sqrt(n))
当n很大时很耗时；

void PrimeNumber(int n, int* primer, int& primer_num)
{
primer_num = 0;
int sqrt_i, i, j;
for (i = 2; i <= n; i++)
{
sqrt_i = (int)sqrt(i);
for (j = 2; j <= sqrt_i; j++)
if (i%j == 0)
break;
if (j > sqrt_i)
primer[primer_num++] = i;
}
}

　２．筛选法：这种方法主要用于打素数表，如求出n之内的所有素数，其思路是从1开始遇到一个素数就标记一下，并去掉n之内的大于它的所有倍数，直循环到n:

此方法也有局限性，数据量中等时才不会超时，数据量过大时也会超时，而且只能用素数打表，不能对单个数进行判定！

void PrimeNumber(int n, int* primer, int& primer_num)
{
    if (n < 2)
    {
        primer_num = 0;
        return;
    }
    primer[0] = 2;
    primer_num = 1;
    for (int i = 1; i < n / 2 + 1; i++)
        primer[i] = true;
    for (int i = 1; i < n / 2 + 1; i++)
    {
        if (primer[i] && (2 * i + 1) <= n)
        {
            primer[primer_num++] = 2 * i + 1;
            for (int j = 3 * i + 1; j < n / 2 + 1; j = j + 2 * i + 1)
                primer[j] = false;
        }
    }
}

3.《离散数学》上的一个定理

• 定理为：“若正整数a>1,且a不能被不超过a的平方根的任一素数整除，则a是素数”，
• 优缺点：此方法可以对超大量数据的进行打表！
  此方法也同样合适于素数打表，判定单个时这个方法不可取！

bool IsPrimerNum(int n, int* primer, int&primer_num)
{
    int sqrt_i= (int)sqrt(n);
    for (int i = 0; primer[i] <= sqrt_i&&primer_num; i++)
    {
        if (n%primer[i] == 0)
            return 0;
    }
    return 1;
}
void PrimeNumber(int n, int* primer, int& primer_num)
{
    primer_num = 0;
    for (int i = 2; i <= n; i++)
        if (IsPrimerNum(i, primer, primer_num))
            primer[primer_num++] = i;
}

参考：http://blog.csdn.net/liukehua123/article/details/5482854
参考：大神http://blog.csdn.net/arvonzhang/article/details/8564836