a007. 判斷質數 - 高中生程式解題系統

題目：

請判斷某數是否為質數

輸入有多組測試資料（以EOF結尾），每組測試資料占一行，只包含一個整數x, 2 ≦ x ≦ 2147483647。

測試資料至多有200000筆。

<aside> 💡

這題要特別注意記憶體及時間(尤其是python)

</aside>

python

def is_prime(a):
    if a < 2:
        return False
    if a in (2, 3):
        return True
    if a % 2 == 0 or a % 3 == 0:
        return False

    # Miller-Rabin test with specific bases for 32-bit integers
    d, s = a - 1, 0
    while d % 2 == 0:
        d //= 2
        s += 1
    
    for i in [2, 7, 61]:
        if i >= a:
            continue
        x = pow(i, d, a)
        if x == 1 or x == a - 1:
            continue
        for j in range(s):
            x = pow(x, 2, a)
            if x == a - 1:
                break
        else:
            return False
    return True

while True:
    try:
        o = int(input())
        if is_prime(o):
            print('質數')
        else:
            print('非質數')
    except:
        break

c++

#include <iostream>#include <cmath>usingnamespace std;
intmain(){
	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;
}