纽芝兰女包是品牌吗:C语言素数问题

来源:百度文库 编辑:神马品牌网 时间:2024/03/28 23:10:15
求100至200间的全部素数。
问题在中间,谢谢解答!!

#include<math.h>
main()
{
int m,i,k,n=0;
for(m=101;m<=200;m=m+2)
{
k=sqrt(m);
for(i=2;i<=k;i++)
if(m%i==0)break;
if(i>=k+1)/**************为何要i>=k+1 而且照道理改成i=k+1范围会更小,奇怪的是i=k+1时反而更多;********************/
{printf(“%d”,m);
n=n+1;}
if(n%n==0)printf(“\n”);
}
printf(“\n”);
}
奇怪就在这个地方,我改成i>k+1 就一个答案也没了。。。。。。
用手算i>=k+1这个条件,105也是符合的,可105又不是素数。
但是i>k+1又没一个是能符合的。。奇怪!!!!!!!!!!!!!!!!!
啊,明白了明白了。。i>=k+1是废的,i==k+1可以的,*的刚才少了一个等号,郁闷啊。
可是所以的版本都是i>=k+1,i根本不会超过k+1呀。。。。。
谁知道!!!!!!!!!!!!!!!!

应该不需要~

我觉得就是i>k就行了~

不过你想想哦!如果N是素数,那么在运行第二个for循环最后最后的第三个语句i++时~i的值会自加1~虽然再下一次无法通过第二个for循环中的判断语句
~但可以肯定的是i肯定大于k+1~所以这样写也完全可以
我想这么写能是为了保险一些吧~其实都一样

if(i>=k+1)/这条语句好象没什么用处~~

定律:在[1, sqrt(n)]不存在一个质数i,使i是n的约数,那么n就是质数。
Theorem: Let n > 1. If n has no prime factor less than or equal to sqrt(n), then n is prime.

#include <stdio.h>
#include <conio.h>
#include <math.h>

int main(void)
{
printf("Prime: %d\n", 1);
printf("Prime: %d\n", 2);

for(int i = 3; i <= 200; i++)
{
int isPrime = 1;
for(int j = 2; j <= sqrt(i + 0.0); j++)
if(i % j == 0) {isPrime = 0; break;}
if(isPrime) printf("Prime: %d\n", i);
}

getchar();
return 0;
}

O(n) < n**2

VC 8下测试通过。