【ZeroJudge】a007 判斷質數 解法分享

點擊前往題目👉a007

我的解法

#include <iostream>
#include <cmath>
using namespace std;
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int g[5000],t=0,root; //g[5000]存放2到2147483647的質數 
	bool b=1;
	root=sqrt(2147483647);
	for(int i=2;i<=root;i++){
		b=1;
		for(int j=2;j<=sqrt(i);j++){
			if(i%j==0){
				b=0;
				break;
			}		
			
		}
		if(b) g[t++]=i;//建表
	}
	
	int n;
	while(cin>>n){
		b=1;
		for(int i=0;i<t;i++){
			int sq=sqrt(n);
			if(sq<g[i]) break;
			if(n%g[i]==0){
				b=0;
				break;
			}
		}
		if(b) cout<<"質數"<<endl;
		else cout<<"非質數"<<endl; 
		
	}
	return 0;
}

解析

在這題我們會需要使用到cmath函式庫，所以請記得

#include <cmath>

這樣我們才能在後面使用到相應的函數。

tips:這裡請不要使用

#include <bits/stdc++.h>

容易TLE

	ios_base::sync_with_stdio(0);
	cin.tie(0);

這段是I/O優化，你可以到這裡查看詳情。

	int g[5000],t=0,root; //g[5000]存放2到2147483647的質數 
	bool b=1;
	root=sqrt(2147483647);
	for(int i=2;i<=root;i++){
		b=1;
		for(int j=2;j<=sqrt(i);j++){
			if(i%j==0){
				b=0;
				break;
			}		
			
		}
		if(b) g[t++]=i;//建表
	}

上面這段旨在建立「質數表」。