懒得用线性筛和埃氏筛

def is_prime(n):
    if n == 1:
        return False
    for i in range(2,int(n**0.5+1)):
        if n%i == 0:
            return False
    return True


n = int(input())
for i in range(1,n+1):
    if is_prime(i):
        print(i)

懒得用线性筛和埃氏筛

详细请见题解 - 【苏州NOI】d029: 求出2－100000之间的所有质数（素数） - TZHSOJ

#include <stdlib.h> 
#include <stdio.h>

int n;

int pow(int x, int y, int z) {
    int res = 1;
    for(; y; y >>= 1) {
        if(y & 1) res = (res % z * x % z) % z;
        x = (x % z * x % z) % z;
    }
    return res;
}

int MillerRabin(int x) {
    int q = x - 1, k = 0;
    while(!(q & 1)) {
        q >>= 1;
        k++;
    }
    int a = rand() % (x - 2) + 2;
    if(pow(a, q, x) == 1) return 1;
    for(int i = 0; i < k; i++) {
        if(pow(a, q, x) == x - 1) return 1;
        q <<= 1;
    }
    return 0;
}

int test(int x) {
	if(x == 2) return 1;
    for(int i = 1; i <= 10; i++) {
        if(!MillerRabin(x)) return 0;
    }
    return 1;
}

int main()
{
    scanf("%d", &n);
    for(int i = 2; i <= n; i++) {
    	if(test(i)) printf("%d\n", i);
	}
    return 0;
}

《极简主义》 for x in [str(i) for i in range(2,int(input())+1) if all(i%j!=0 for j in range(2,int(i**0.5)+1))]:print(x)

#include<bits/stdc++.h>//总思想，是一个数字一个数字*递进*进行筛去
using namespace std;
const int N=1000010;
int  prime[N];
int cnt;
bool st[N];
void get_prime(int n)
{
    for(int i=2;i<=n;i++)
    {
        if(!st[i])//如果这个数字未被筛掉,那么作为质数存入
       {
           prime[cnt]=i;
           cnt++;
       }
       for(int j=2*i;j<=n;j+=i){
           st[j]=true;//将当前已经筛过的i的倍数全部标记为筛去 再递进到下一个数，下一个数也是同理，无论是否被存入数组，都应筛去其倍数//详见其原理
       }
       
    }
}


int main()
{
    int n;
    cin>>n;
    get_prime(n);
   for(int i=0;i<cnt;i++){
       cout<<prime[i]<<endl;
   }
}

优化

#include<bits/stdc++.h>//总思想，是一个数字一个数字*递进*进行筛去
using namespace std;
const int N=1000010;
int  prime[N];
int cnt;
bool st[N];
void get_prime(int n)
{
    for(int i=2;i<=n;i++)
    {
        if(!st[i])//如果这个数字未被筛掉,那么作为质数存入
       {
           prime[cnt]=i;
           cnt++;   
 for(int j=2*i;j<=n;j+=i){           st[j]=true;//将所有素数的倍数删去即可，无需遍历2~p-1所有数   }
       }
   
       
    }
}


int main()
{
    int n;
    cin>>n;
    get_prime(n);
   for(int i=0;i<cnt;i++){
       cout<<prime[i]<<endl;
   }
}

C++ :

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cctype>
#define Maxn 1009
using namespace std;
bool a[Maxn],b[Maxn];
int main()
{   int n;
    scanf("%d",&n);
    memset(a,true,sizeof(a));
    int m=2;
    while(m<=1000){
        while(a[m]==false && m<=1000){m++;}
        int k=2;
        while(m*k<=1000){
            a[m*k]=false;
            k++;
        }
        m++;
    }
     for(int i=2;i<n;i++){
       if(a[i]==true) printf("%d\n",i);
     }





    return 0;
}