Re: [問題]1到10000之間求質數的程式如何寫?
※ 引述《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
推
04/08 10:24, , 1F
04/08 10:24, 1F
→
04/08 10:26, , 2F
04/08 10:26, 2F
推
04/08 10:28, , 3F
04/08 10:28, 3F
→
04/08 10:29, , 4F
04/08 10:29, 4F
→
04/08 10:30, , 5F
04/08 10:30, 5F
→
04/08 10:31, , 6F
04/08 10:31, 6F
→
04/08 10:33, , 7F
04/08 10:33, 7F
推
04/08 12:26, , 8F
04/08 12:26, 8F
→
04/08 12:27, , 9F
04/08 12:27, 9F
推
04/08 12:34, , 10F
04/08 12:34, 10F
→
04/08 13:06, , 11F
04/08 13:06, 11F
→
04/08 13:08, , 12F
04/08 13:08, 12F
推
04/08 13:49, , 13F
04/08 13:49, 13F
→
04/08 13:50, , 14F
04/08 13:50, 14F
推
04/08 14:20, , 15F
04/08 14:20, 15F
推
04/08 14:23, , 16F
04/08 14:23, 16F
推
04/08 14:28, , 17F
04/08 14:28, 17F
推
04/08 17:35, , 18F
04/08 17:35, 18F
推
04/08 18:04, , 19F
04/08 18:04, 19F
推
04/09 15:08, , 20F
04/09 15:08, 20F
→
04/09 15:10, , 21F
04/09 15:10, 21F
※ 編輯: BETNPP 來自: 220.133.102.247 (04/09 15:18)
C_and_CPP 近期熱門文章
PTT數位生活區 即時熱門文章
