判断素数最快的方法_模6法判断素数

判断素数最快的方法

1、普通方法

bool is_prime(int n)
{
    if (n < 2)
        return false;
    int i;
    for (i = 2; i < n; i++)
    {
        if (n % i == 0)
        {
            return false;
        }
    }
    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

原理是对每个数进行开方，模运算。
我们来统计0~100000之间有多少素数，并计算程序运行的时间。

int main()
{
    clock_t start, finish;
    double totaltime;
    start = clock();
    int n = 0;
    for (int i = 0; i < 100000; i++)
    {
        if (is_prime(i))
        {
            n++;
        }
    }
    cout << "n = " << n << endl;
    finish = clock();
    totaltime = (double)(finish - start) / CLOCKS_PER_SEC;
    cout << "\n此程序的运行时间为" << totaltime << "秒！" << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

运行结果如下：

n = 9592
此程序的运行时间为1.244秒！
1
2

平时需求不太大，勉勉强强能接受这个速度吧。
但是范围增加到0~1000000，

for (int i = 0; i < 1000000; i++)
1

n = 78498
此程序的运行时间为102.255秒！
1
2

这个时间太长了。如果数据量再大一点，那我岂不是要等到天荒地老？

2、目前我发现的最快的方法

n>3时，对一个数字进行模6运算，如果结果是0,2,3,4，那么这个数肯定不是素数。

这样就节省了2/3的工作量。

接下来和第一种方法类似，不过是从5开始，步长为6，
除数i和i+2都是奇数并且都是质数，这又减少了特别多的工作量。

bool is_prime(int num)
{
    if (num <= 3)
        return num > 1;
    if (num % 6 != 1 && num % 6 != 5)
        return false;
    int s = sqrt(num);
    for (int i = 5; i <= s; i += 6)
        if (num % i == 0 || num % (i + 2) == 0)
            return false;
    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12

现在运行一下0~100000的结果：

for (int i = 0; i < 100000; i++)
1

a = 9592
此程序的运行时间为0.005秒！
1
2

0.005秒，跟1.244秒比，速度是原来的248.8倍。

接下来

for (int i = 0; i < 1000000; i++)
1

n = 78498
此程序的运行时间为0.064秒！
1
2

0.064秒相比于102.255秒，速度增加1597.7倍！简直是一个天上一个地下。

接下来再增大范围：

for (int i = 0; i < 10000000; i++)
1

n = 664579
此程序的运行时间为1.43秒！
1
2

for (int i = 0; i < 100000000; i++)
1

n = 5761455
此程序的运行时间为36.375秒！
1
2

行了行了，到此为止。