作者BETNPP (NPP)
看板C_and_CPP
标题Re: [问题]1到10000之间求质数的程式如何写?
时间Sun Apr 8 04:47:15 2007
※ 引述《iwantnasa (红发杰克)》之铭言：
: 我想知道1~10000之间的质数用C++如何找
: 老师建议用辗转相除法
: BUT我一点头绪都没有
: 目前只会FOR回 圈和DO-while
: 不会副程式
: 各位能用简单的程式教教我吗?
#include <stdio.h>
int main(){
//-- 先设一个很大的阵列用来放质数
int p[10000];
//--在宣告一个int变数来记录已经放了多少个质数
int n=2;
//--宣告回圈所需的index
int num,i;
//--宣告一个state记录是否为PRIME
int prime;
//--然後先把2跟3放入
p[0]=2; p[1]=3;
//--根据质数的定义除了1跟自己以外没有其他的因数
// ＝>不会被小於自己的质数整除
//用回圈来控制此条件
for(num=4;num<10000;num++){
//小於10000的数中依序取一数num
for(prime=1,i=0;i<n;i++){
//在比num小已知的prime number数列中
if( num%p[i] == 0){
//如果取余数为零（整除）
prime=0;
//则不为质数
break;
}
}
if(prime == 1){
//如果在比num小已知的prime number数列中都不能整除
p[n++]=num;
//则num为余数，n个数+1
}
}
for(i=0;i<n;i++)
fprintf(stdout,"
%5d",p[i]);
return 0;
}
ps. 这只是我想到的一种方法而已，当然也可以不要储存利用GCD来求.....
例如，一个数n为质数 => GCD(n,i)=1,for all 1＜i≦√n i为整数
很多解法......都可以达到同样效果～多练习看看罗～
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.121.213.202
1F：推 revivalworld:建议把 sqrt() 用进去, 还有回圈的 num++改成 num+=2 04/08 10:24
2F：→ revivalworld:这个演算法似乎太暴力了点- -" 04/08 10:26
3F：推 revivalworld:再给一个建议, 听过质数的规谬证明吧 04/08 10:28
4F：→ revivalworld:你可以把已知的质数乘起来 然後+1 就是一个新的质数 04/08 10:29
5F：→ revivalworld:当然要从最小的2开始乘，中间不可漏掉任何质数 04/08 10:30
6F：→ revivalworld:嗯...是"归谬" 04/08 10:31
7F：→ revivalworld:话说质数证明好像跟这篇没太大关系...不要理我Orz 04/08 10:33
8F：推 ledia:全乘起来+1 还是质数是错的 2*3*5*7*11*13+1 = 59*509 04/08 12:26
9F：→ ledia:不要误导别人.... 04/08 12:27
10F：推 ledia:你可能搞不清楚归谬的本质 04/08 12:34
11F：→ compbell:楼上是对的，上述证法有假设"质数为有限个"，然後得矛盾 04/08 13:06
12F：→ compbell:但可没说已知的质数乘起来+1会是质数 04/08 13:08
13F：推 xcycl:冼镜光《C名题精选百则》有很详尽的讨论 @@ 04/08 13:49
14F：→ xcycl:不过才一万个, 暴力法也是瞬间解吧 XD 04/08 13:50
15F：推 revivalworld:对不起...我搞错了 04/08 14:20
16F：推 revivalworld:谢谢您指出来 04/08 14:23
17F：推 revivalworld:再推一次表示歉意 04/08 14:28
18F：推 iwantnasa:能用辗转吗? 04/08 17:35
19F：推 slalala:可辗转喔~更快~~如果现在的CPU跟RAM很小很慢 暴力法会?!XD 04/08 18:04
20F：推 BETNPP:嗯....用+=2的确会快近两倍，不过我只是单纯的用数学的判断 04/09 15:08
21F：→ BETNPP:慢慢的推而已，我想应该有更好更快的演算法..... 04/09 15:10
※ 编辑: BETNPP 来自: 220.133.102.247 (04/09 15:18)