判斷質數

最近拿了"高中生程式解題系統"來練習我的c programming， 才做到第七題就碰到瓶頸了，題目是要判斷質數，但我在測資的時候都會愈時，於是在網路上參考了許多人的分享，花了我將近一個星期的時間，最後終於拿到AC了.ㄎㄎ~其實看到網路上滿多人分享這題的解法的，但是有的跑出來還是怪怪的。以下分享參考網路上的資料後自己再重寫的程式碼。


首先是6N+1,6N-1法，但這個在zerojudge測資會愈時，不過平常拿來玩玩也是堪用的

	#include<iostream>
	#include<math.h>
	using namespace std;
	int main(){
	int a;
	while(cin >> a){
	int b = 0;
	if(a==2 || a==3){
	cout << "質數" << endl;
	}
	else if (a%2==0 || a%3==0){
	cout << "非質數" << endl;
	b = 1;
	}else{
	int a_sqrt =sqrt(a);
	for (int i = 5, gap=2; i <= a_sqrt; i+=gap, gap=6-gap){
	if (a%i==0){
	cout << "非質數" << endl;
	b = 1;
	break;
	}
	}
	if(b==0){
	cout << "質數" << endl;}
	}
	}
	return 0;
	}

view raw prime.cpp hosted with ❤ by GitHub

第二個方法是用埃拉托斯特尼篩法(sieve)建質數表，測資1.4s過 (雖然不算最快的..XD)

	#include<iostream>
	#include<math.h>
	using namespace std;
	int prime[5150]={0};
	void findPrime(){
	char judge[50000]={0};
	int m = 0;
	for (int a = 2; a<=50000; a++){
	if (judge[a]==0){
	prime[m++]= a;
	for (int b=2; b*a<=50000; b++){
	judge[b*a]=1;
	}
	}
	}
	}
	bool is_prime(int num){
	int num_sqrt =sqrt(num);
	for(int i=0; prime[i]<=num_sqrt;i++){
	if (num%prime[i]==0&&num/prime[i]!=1){
	return false;
	}
	}return true;
	}
	int main(){
	findPrime();
	int a;
	while (cin >> a){
	if(is_prime(a)){
	cout << "質數" << endl;
	}else {
	cout << "非質數" << endl;
	}
	}
	return 0;
	}

view raw sieve_findPrime.cpp hosted with ❤ by GitHub