Zerojudge a007
題敘
https://zerojudge.tw/ShowProblem?problemid=a007
多筆測資,給一個數,求是否為質數
想法
對於一個數 $N$ ,只需要判斷 $2$ ~ $\sqrt{N}$ 的質數,是否有能整除 $N$ 的即可
如果有,則非質數
預先將 $0$ ~ $\sqrt{2147483647}$ 的質數表建立起來,對於每次輸入再一一判斷即可
Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38
| #include<bits/stdc++.h> #define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); #define ll long long #define pii pair<int,int> using namespace std; bool prime[47000]; vector<int> primes; int n,sq=sqrt(2147483647); int main(){ IOS; for(int i=0 ; i<sq ; i++){ prime[i]=true; } prime[0]=prime[1]=false; for(int i=2 ; i<sq ; i++){ if(prime[i]){ primes.push_back(i); for(int j=i*i ; j<sq ; j+=i){ prime[j]=false; } } } while(cin>>n){ int sq=sqrt(n); bool is_prime=true; for(auto i: primes){ if(i>=sq) break; if(n%i==0){ is_prime=false; break; } } if(is_prime && n!=1) cout<<"質數\n"; else cout<<"非質數\n"; } return 0; }
|
複雜度
預處理時間複雜度約略為 $O(\sqrt{N}^2)$
而每筆處理時間複雜度約為 $O(N)$
總複雜度約為 $O(N)$