送大家一份筛素数模板~

wffms69_8 @ 2016-08-20 17:11:33

#include<vector>
#include<cstdio>
#include<cstring>
using namespace std;

vector<int>Eratosthenes(int n) {
    bool visit[n];
    memset(visit, 0, sizeof visit);
    for (int i(2); i * i < n; ++i)
        if (!visit[i])
            for (int j(i * i); j < n; j += i)
                visit[j] = true;
    vector<int>result;
    for (int i(2); i < n; ++i)
        if (!visit[i])
            result.push_back(i);
    return result;
}

int main() {
    int n;
    scanf("%d", &n);
    vector<int>prime(Eratosthenes(n));
    for (int i(0); i < prime.size(); ++i)
        for (int j(i); j < prime.size(); ++j)
            for (int k(j); k < prime.size(); ++k)
                if (prime[i] + prime[j] + prime[k] == n) {
                    printf("%d %d %d\n", prime[i], prime[j], prime[k]);
                    return 0;
                }
}

by infinityedge @ 2016-08-21 09:05:53

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
bool IsPrime[1000001];
int Pri[3000001],PriN=0,n;
int FindPrime ( int MaxN ) {
    memset(IsPrime,1,sizeof(IsPrime));
    for( int i = 2 ; i <= MaxN ; ++i ) {
        if( IsPrime[ i ] )
            Pri[ ++PriN ]=i;
        for(int j=1; j<=PriN; j++) {
            if( i*Pri[ j ] > MaxN )
                break;
            IsPrime[ i * Pri[ j ] ] = 0;
            if( i % Pri[ j ] == 0 ) break;
        }
    }
}
int main() {
    cin>>n;
    FindPrime(n);
    for(int i=1;i<=PriN;i++){
        printf("%d ",Pri[i]);
    }
    return 0;
}

by Aimyhtixela @ 2016-08-21 09:25:50

#include <iostream>
using namespace std;
bool judge_prime(int a){
    for (int i=2;i*i<=a;++i){
        if (a%i==0){
            return false;
        }
    }
    return true;
}
int main(){
    int n;
    cin>>n;
    if (judge_prime(n)==true && n!=1){
        cout<<"TRUE"<<endl;
    }
    else {
        cout<<"FALSE"<<endl;
    }
    return 0;
}

by ccviolett @ 2016-09-11 09:13:08

欧拉线性筛，新手初学勿吐槽

#include <stdio.h>
int zs[20001],top;
bool arrive[20000];
int main(){
    int i,j,k,n;
    scanf("%d",&n);
    for(i=2;i<=n;i++){
        if(!arrive[i])   zs[++top]=i;
        for(j=1;j<=top;j++){
            if(zs[j]*i>n)   break;
            arrive[zs[j]*i]=true;
            if(!(i%zs[j]))  break;
        }
    }
    for(i=1;i<=top;i++){
        for(j=1;j<=top;j++){
            for(k=1;k<=top;k++){
                if(zs[i]+zs[j]+zs[k]==n){
                    printf("%d %d %d\n",zs[i],zs[j],zs[k]);
                    return 0;
                }
            }
        }
    }
    return 0;
}

by 我爱编程 @ 2017-04-25 21:56:50

以后炫耀也可以加个注释啊。

by 我爱编程 @ 2017-04-25 21:57:12

表示自己并没有看懂