2016年11月5日 星期六

TIOJ 1659 - 找質數

http://tioj.infor.org/problems/1659

 那時候好像還不會$O(n)$的寫法
....不過這複雜度是啥阿(
不會算(

 

 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
39
40
41
42
43
44
45
46
47
#include<bits/stdc++.h>
using namespace std;
#define PB(x) push_back(x)

inline int rit(){
    int t=0,k=1;
    char c;
    do{
        c=getchar();
        if(c=='-')k=-1;
    }while(c<'0'||c>'9');
    do{
        t=t*10+c-'0';
        c=getchar();
    }while(c>='0'&&c<='9');
    return t*k;
}

vector<int> p;
int n,tryto,i;
bool d;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    p.PB(2);
    p.PB(3);
    p.PB(5);
    for(tryto=6;tryto<=5123;tryto++){
        d=0;
        for(i=2;i*i<=tryto;i++){
            if(tryto%i==0){
                d=1;
                break;
            }
        }
        if(!d){
            p.PB(tryto);
        }
    }
    while(cin>>n){
        cout<<"primes between 1 ~ "<<n<<":";
        for(i=0;p[i]<=n && i<(int)p.size();i++){
            cout<<' '<<p[i];
        }
        cout<<'\n';
    }
}
張貼者： 於

沒有留言:

張貼留言

訂閱： 張貼留言 (Atom)