审计案例文库:质疑素数的"优化"判别方法!

来源:百度文库 编辑:中科新闻网 时间:2024/03/29 15:28:55
质疑素数的"优化"判别方法!

CODE:[Copy to clipboard]
#include<stdio.h>
int main()
{

int n,i,k; /* Verson 1*/
scanf("%d",&n); /* by Sai from:bbs.pczero.cn*/
for(i=2;i<n;i++){ /*我写的效率就不高?,偶看未必!当n是合数时也就是只要当k第一次被整除时~就break拉*/
k=n%i;
if(k==0)break;
else break;
}

if(k==0)
printf("%d is not a prime",n);
else
printf("%d is a prime",n);

}

传统的"优化"方法:
CODE:[Copy to clipboard]#include"stdio.h"
#include"math.h"
int main()
{
int m,i,k; /*Verson 2*/
/* by Sai from:bbs.pczero.cn */
scanf("%d",&m); /* Sai's Blog:www.phoenixonline.cn/blog*/
k=sqrt(m);
for(i=2;i<=k;i++)
if(m%i==0)break;

if(i>k)
printf("%d is a prime number",m);

else
printf("%d isn't a prime number",m);

}

但是当n一直没有整除的时候呢?你会循环n-2次哦!比传统的"优化"方法的循环次数要多,效率问题就不用说了.

其实可以继续优化的,
for语句后面这么写:
for(i=2;i<=sqrt(k);i++)要比原算法快些,因为从2判断到根号K就可以了,后面的都不必要,要是不能被2到根号K整除那么也不能被后面的整除。