大学IT网 - 最懂大学生的IT学习网站! QQ资料交流群:367606806
当前位置:大学IT网 > C技巧 > 素数的高效算法

素数的高效算法(1)

关键词:素数高效算法  阅读(1112) 赞(14)

[摘要]本文是对素数的高效算法的讲解,与大家分享。

自然数(Natural Number):自然数就是正整数集合,用{1, 2, 3, ...}表示,也可以是非负整数集合,用{0, 1, 2, 3, ...}表示,前都主要用于数论,后者则主要用于数理逻辑、集合论、计算机科学等。

素数():素数一个大于1的自然数,该自然数只有1和它本身两个除数(自然数)。

这概念虽然简单,但如果不知道的话程序写将无从下手,这无异于“James, 给我写个满足要求的程序", 但并没有说写什么样的程序。

典型算法

最简单最直接的方法应该就是用2到(n-1)的自然数去除n,其中n即为将要确实是数,如果每个数都不能整除,则说明n是素数。

而事实上没有必要用2到(n-1)之间的每一个数去除n。例如要确实7是不是系数,用除到3的时候就已经可以确实7是系数而不必继续了,即只要用2,3去除n就可以了。一般地,只要用2到n/2的自然数去除n就可以了。这样比前面的方法要快一点。

人们还想到了一个更好一点方法:用来取代n/2。

今天同学考试的问题是:给定两个整数m,k,找出大于m同时也最靠近m的k个素数,用C语言实现如下:
void findPrimeNum(int m, int k , int xx[]) {
int i = 0, j, x = m + 1, isPrime;
while (i < k) {
isPrime = TRUE;
for ( j = 2; j <= sqrt(x); j++) { // j <= 2 也行
if ( x % j == 0 ) {
isPrime = FALSE;
break;
}
}
if (isPrime) xx[i++] = x;
x++;
}
}


更有效的算法

如果给定一个很大的自然数要确定其是否为素数,典型算法可能要费很多的时间才能确定下来。这里有一个更好一点的算法:
boolean isPrime(int num) {

int divisor = 3;
int testLimit = num;

if (num % 2 == 0) return FALSE;

while ( testLimit > divisor ) {
if ( num % divisor == 0 ) {
return FALSE;
}

testLimit = num / divisor;
divisor += 2;
}

return TRUE;
}

程序实现

«上一页12下一页»


相关评论