题解 | #素数#

法一：朴素筛法

#include <bits/stdc++.h>

const int N = 10010;
int primes[N], cnt;     // primes[]存储所有素数
bool st[N];         // st[x]存储x是否被筛掉

// 朴素筛法 
void get_primes(int n){
	for (int i=2; i<=n; i++){
		if (!st[i]){
			primes[cnt] = i;
			cnt ++; 	
		}
		for (int j=i+i; j<=n; j+=i){
			st[j] = true;
		}
	}
}

int main(){
	int n;	
	while (scanf("%d", &n) != EOF){
		if (n <= 11){
			printf("-1\n");
			continue;
		}
		get_primes(n);
		for (int i=0; i<=cnt; i++){
			if (primes[i] % 10 == 1 && primes[i] != n){
				printf("%d ", primes[i]);
			}
		}
		printf("\n");
	}
	return 0;
}

法二：埃式筛法

#include <bits/stdc++.h>

const int N = 10010;
int primes[N], cnt;     // primes[]存储所有素数
bool st[N];         // st[x]存储x是否被筛掉

// 埃式筛法
void get_primes(int n) {
    for (int i = 2; i <= n; i++) {
        if (!st[i]) {
            primes[cnt] = i;
            cnt ++;
            for (int j = i + i; j <= n; j += i) {
                st[j] = true;
            }
        }
    }
}

int main() {
    int n;
    while (scanf("%d", &n) != EOF) {
        if (n <= 11) {
            printf("-1\n");
            continue;
        }
        get_primes(n);
        for (int i = 0; i <= cnt; i++) {
            if (primes[i] % 10 == 1 && primes[i] != n) {
                printf("%d ", primes[i]);
            }
        }
        printf("\n");
    }
    return 0;
}

法三：线性筛法

#include <bits/stdc++.h>

const int N = 10010;
int primes[N], cnt;     // primes[]存储所有素数
bool st[N];         // st[x]存储x是否被筛掉

// 线性筛法
void get_primes(int n) {
    for (int i = 2; i <= n; i++) {
        if (!st[i]) {
            primes[cnt] = i;
            cnt ++;
        }
        for (int j=0; primes[j]<=n/i; j++){
            st[primes[j] * i] = true;
            if(i % primes[j] == 0) break; 
        }
    }
}

int main() {
    int n;
    while (scanf("%d", &n) != EOF) {
        if (n <= 11) {
            printf("-1\n");
            continue;
        }
        get_primes(n);
        for (int i = 0; i <= cnt; i++) {
            if (primes[i] % 10 == 1 && primes[i] != n) {
                printf("%d ", primes[i]);
            }
        }
        printf("\n");
    }
    return 0;
}