三种方法求质数：
一、原理：每个合数都可以被质数整除；
1.把每个求出的质数存放在数组str[]中， 2.合数i整除数组中的质数， 3.将数组最后的数传给x； 4.再让i除x直到除到i-1； 5.再把i放入数组中；
void sushu
(int str
[N
]);
int main
()
{
int str
[N
]={'1'};//将str初始化都为1；
sushu
(str
);
return 0
;
}
void sushu
(int str
[N
])
{
int i
=2,j
=0,k
=0,x
=0,p
=0,z
=0
;
int n
;
printf
("输入需要素数的范围\n");
scanf
("%d",
&n
);
str
[0
]=2
;
while
(i
<=n
)
{
j
=0
;
p
=1
;
while
(j
<k
)
{
if
(i%str
[j
]==0
)
{
p
=0
;
break;
}
j++
;
}
x
=str
[j-1
];
while
(x
<=i-1
)
{
if
(i%x
==0
)
{
p
=0
;
break;
}
x++
;
}
if
(p
==0
)
{
i++
;
continue;
}
str
[k
]= i
;
i++
;
k++
;//k获取素数数组的最大角标
}
while
(z
<k
)
{
printf
("%d ",str
[z
]);
z++
;
}
}
优点：
质数放在 数组str中，可以被调用；
缺点：
只能算出0~1000以内的质数；
二、原理：从j=2开始递增依次判断是否有j可以被i整除
int main
()
{
int i,j,k
=0
;
for
(i
=2
;i
<1000000000000000000000000000000000000000000000000000000000000000
;i++
)//64位
{
for
(j
=2
;j*j
<=i
;j++
)
if
(i%j
==0
)
break;
if
(j*j
>i
)
{
printf
("%d ",i
);
k++
;
if
(k%5
==0
)
printf
("\n");
}
}
}
优点：
可以判断2~10（64次方）之间的质数；
缺点：
判断出的数值无法被调用：
三、原理：去除素数的倍数筛选质数，与原理一类似；
void prime
(int n
);
int str
[N
];
int main
()
{
int i,n
;
printf
("输入一个数判断是否是质数\n");
scanf
("%d",
&n
);
prime
(n
);
for
(i
=2
;i
<=n
;i++
)
if
(str
[i
])//判断值数；
printf
("%d ",i
);
return 0
;
}
void prime
(int n
)
{
int i,j,m
;
for
(i
=2
;i
<=n
;i++
)
str
[i
]=1
;
str
[0
]=str
[1
]=0
;
m
=sqrt
(n
);
for
(i
=2
;i
<=m
;i++
)
{
if
(str
[i
])
for
(j
=2*i
;j
<=n
;j
=j+i
)//筛选素数的整数倍：
str
[j
]=0
;
}
}
优点：
1.可以计算0~100000000（一亿）；
2.可对一个数进行单独判断是否是质数并调用；
缺点：
1.数据利用率不高，不能直接大批量调用；
