首页 > 试题广场 >

筛选法求素数

[编程题]筛选法求素数

热度指数：30324 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

$\hspace{15pt}$ 使用下方所描述的筛选法，求解 $n$ 以内的全部素数，同时输出被置为 $0$ 的整数个数。

$\hspace{15pt}$ 筛选法求解的过程为：
${\hspace{20pt}}_\texttt{1.}\,$ 将 $2$ 到 $n$ 之间的整数放在数组内存储；
${\hspace{20pt}}_\texttt{2.}\,$ 将数组中 $2$ 之后的所有能被 $2$ 整除的数置为 $0$ ；
${\hspace{20pt}}_\texttt{3.}\,$ 将数组中 $3$ 之后的所有能被 $3$ 整除的数置为 $0$ ；
${\hspace{20pt}}_\texttt{4.}\,$ ……；以此类推，直到将数组中 $n$ 之后的所有数都置为 $0$ 为止；
${\hspace{20pt}}_\texttt{5.}\,$ 此时，数组中剩余的非 $0$ 的数即为 $n$ 以内的全部素数。

【名词解释】
$\hspace{15pt}$ 素数：也称质数。一个大于 $1$ 的正整数，如果除了 $1$ 和它自身以外不再有其他因数，那么这个数被称作素数。特殊地， $1$ 既不是素数也不是合数。

输入描述:

在一行上输入一个整数 。

输出描述:

第一行输出若干个整数，表示  以内的全部素数，用空格分隔。
第二行输出一个整数，表示被置为  的整数个数。

示例1

输入

输出

2 3 5 7 11 13 17 19
11

算法知识视频讲解

C++

virteki73

#include <iostream>
using namespace std;
const int N = 110;
int primes[N], st[N], cnt;
void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (st[i]) continue;
        primes[cnt ++ ] = i;
        for ( int j = i + i; j <= n; j += i) st[j] = 1;
    }
}


int main()
{
    int n;
    get_primes(100);
    while (cin >> n)
    {
        int count = 0;
        for (auto c : primes)
        {
            if (c > n) break;
            count ++;
            cout << c << ' ';
        }
        cout << endl;
        cout << n - count - 1 << endl;
    }
}

发表于 2022-02-26 14:43:33 回复(0)

C++

东风街大饼

#include<bits/stdc++.h>
using namespace std;

int vis[300];

void isp(){
    int m = sqrt(300 + 0.5);
    for(int i=2;i<=m;i++) if(!vis[i])
        for(int j=i*i;j<=300;j+=i) vis[j] = 1;
}

int cnt;

int main(){
    isp();
    int n;
    cin>>n;
    for(int i=2;i<=n;i++) if(!vis[i]){
        printf("%d ",i);
        cnt++;
    }
    printf("\n");
    printf("%d",n-cnt);
    return 0;
}

发表于 2022-02-09 15:20:36 回复(0)

C++

别样的人儿

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    int count = 0; // 质数的数目
    while(cin>>n){
        for(int i=2; i<n; i++){
            bool flag = true; // 是否是质数标志
            for(int j=2; j<i; j++){
                if(i%j==0){
                    flag=false;
                    break;
                }
            }
            if(flag == true){
                cout<<i<<" ";
                count++;
            }
        }
        cout<<endl;
        cout<<n-count-1;
    }
    return 0;
}

发表于 2022-01-21 17:03:58 回复(0)

阿金要努力

#include <stdio.h>
int main()
{
	int n = 0,count = 0;
	while (~scanf("%d", &n))
	{
		int arr[100] = { 0 };
		for (int i = 0; i <n-1; i++)
		{
			arr[i] = i+2;
            for (int j =2; j <arr[i]; j++)
			{
				if (arr[i] % j == 0)
				{
					arr[i] = 0;
					break;
				}
			}
		}
		for (int i = 0; i <n-1; i++)
		{
			if (arr[i] != 0)
				printf("%d ", arr[i]);
			else
				count++;
		}
		printf("\n%d\n", count);
	}
	return 0;
}

发表于 2021-12-26 01:19:18 回复(0)

夕染浅青

using namespace std;
int main()
{
    int n,k,num=0;
    cin>>n;
    for(int i=2;i<n;i++){
        k=0;
        for(int j=i-1;j>=2;j--){
            if(i%j==0)
                k++;
        }
        if(k==0){
            cout<<i<<" ";
            num++;
        }
        
    }
    cout<<"\n"<<(n-num-1);

    return 0;
}

发表于 2020-09-24 16:59:24 回复(0)

敲码挣钱

#include<stdio.h>
int main()
{
	int a[100],cnt=0,i,n,j;
	while(scanf("%d",&n)!=EOF){
	cnt=0;
	for(i=0;i<=n;i++){
		a[i]=i;
	}
	for(i=2;i<n;i++){//让整个数组分别除以23456。。。判断，且不除以本身
		for(j=4;j<=n;j++){
			if(a[j]%i==0&&i!=j)
			a[j]=0;
		}
	}
	
	for(i=2;i<=n;i++){//输出符合条件的素数
		if(a[i]!=0){
			printf("%d ",a[i]);
		}else
		cnt++;
	}
	printf("\n%d\n",cnt);
    }
/*for(i=0;i<n;i++)
printf("%d ",a[i]);
	
}*/
	
	
	return 0;
}

发表于 2021-07-31 18:29:22 回复(0)

牛客688983736号

#include <stdio.h>

int main(){
    int n, arr[20];
    int count, count_i = 0;
    scanf("%d", &n);
    for(int i = 2; i <= n; i++){
        count_i = 0;
        for(int j = 1; j <= i; j++){
            if(i % j == 0)
                count_i++;
        }
        if(count_i == 2){
            arr[count] = i;
            count++;
        }
    }  
    for(int i = 0; i < count; i++){
        printf("%d ", arr[i]);
    }
    printf("\n%d", n - count - 1);
    return 0;
}

发表于 2022-06-07 15:09:40 回复(0)

Python 3

新的一天，啦啦啦

n = int(input())
res_list = [2]
    
def isNum(number):
    flag = True
    for i in range(2, number):
        if number % i == 0:
            flag = False
    return flag

for i in range(3, n+1, 2):
    is_num = isNum(i)
    if is_num:
        res_list.append(i)

print(*res_list)
print(n - len(res_list) - 1)

发表于 2022-07-11 09:51:50 回复(0)

时影Sakura

#include<stdio.h>
int main()
{
    int n , a[100] , k = 2 , count = 0;
    while(scanf("%d",&n) != EOF)    //多组输入，每行输入一个正整数
    {
        for(int i = 0 , j = 2; j < n ; i++ , j++) a[i] = j;    //将 2 ~ n 之间的正整数放在数组内存储
        
        for(int i = 0 ; i < n - 1 ; i++)
        {
                for(int j = i + 1 ; j < n - 1 ; j++)    //遍历数组中 k 值之后的所有元素
                {
                    if(a[j] % k == 0)
                        a[j] = 0;    //将数组中 k 之后的所有能被 k 整除的数清 0 
                }
                k++;
        }
        for(int i = 0 ; i < n - 1 ; i++)
        {
            if(a[i] != 0)
            {
                count++;
                printf("%d ",a[i]);
            }
        }
        printf("\n%d\n",n - 1 - count);
    }
    return 0;
}

发表于 2022-06-27 14:08:44 回复(0)

美美哒蔡蔡子

#include<stdio.h>
int main()
{
int n,ch[100],i,j,num=0;
while(scanf("%d",&n)!=EOF)
{
for(i=2;i<=n;i++)
{
ch[i]=i;}
for(i=2;i<=n;i++)
{for(j=i+1;j<=n;j++)
{if(ch[j]%i==0)
ch[j]=0;
}
}
}
for(i=2;i<=n;i++)
{if(ch[i]!=0)
printf("%d ",ch[i]);
if(ch[i]==0)
num++;
}
printf("\n");
printf("%d\n",num);

}

发表于 2020-06-08 13:54:39 回复(0)

C++

不放弃的咸鱼很伟大

#include <iostream>
using namespace std;

int main() {
    int a, b;
    while(cin>>a)
    {
    int arr[a];
    int num=0;
    for(int i=0;i<a-1;i++)
    {
        arr[i]=i+2;
    }
    for(int i=1;i<a-1;i++)//i表示在数组中的位置
    {
        for(int j=2;j<a;j++)//j表示要判断素数时除的数
        {
            if(i>=j-1&&arr[i]%j==0&&arr[i]!=0)//arr[i]!1=0是要保证数组中已经清0的数重复清0
            {
                arr[i]=0;
                num++;
            }  
        }
    }

    for(int i=0;i<a-2;i++)
    {
        if(arr[i]!=0)
        {
            cout<<arr[i]<<" ";
        }
    }
    cout<<endl;
    cout<<num<<endl;
    }
}

发表于 2025-09-11 21:12:57 回复(0)

鲸鱼lord

#include <stdio.h>

#include <math.h>

int main() {

int num=0;

int arr[101]={0};

while(scanf("%d",&num)!=EOF)

{

//数组赋值

for(int i=2;i<=num;i++)

{

arr[i]=i;

}

//筛选

for(int i=2;i<=num;i++)

{

//缩小试除范围

for(int j=2;j<=sqrt(i);j++)

{

if(i%j==0)

{

//不是素数

arr[i]=0;

}

int count=0;

for(int i=2;i<=num;i++)

{

if(arr[i]!=0)

{

printf("%d ",arr[i]);

}

else {

count++;

}

printf("\n%d",count);

}

return 0;

}

发表于 2025-08-24 12:39:25 回复(0)

诗奕

#include <stdio.h>

int main() {
    int n = 0;
    while (scanf("%d", &n) != EOF) {
        int arr[101];
        int i = 0;
        //存储数据
        for (i = 2; i <= n; i++) {
            arr[i] = i;
        }
        int j = 0;
        for (j = 2; j <= n; j++) {
            int k = 0;
            for (k = j + 1; k <= n; k++) {
                if (arr[k] % j == 0) {
                    arr[k] = 0;
                }
            }
        }
        int count = 0;
        for (i = 2; i <= n; i++) {
            if (arr[i] != 0)
                printf("%d ", arr[i]);
            else
                count++;
        }
        printf("\n%d\n", count);
    }
    return 0;
}

发表于 2024-01-17 20:51:18 回复(0)

时不语ac

#include <stdio.h>
int main()
{
    int n = 0;
    int arr[101] = {0};
    while(scanf("%d",&n)!=EOF)
    {
        int k = 2,count = 0;
        while(k<=n)
        {
            for(int i = k+1;i<=n;i++)
            {
                if(i%k==0) arr[i] = 1;
            }
            k++;
        }
        for(int i = 2;i<=n;i++)
        {
            if(arr[i] == 0) printf("%d ",i),count++;
            else arr[i] = 0;
        }
        printf("\n%d\n",n-2+1-count);//总数减素数个数为筛去个数
    }
    return 0;
}

发表于 2023-03-14 21:54:59 回复(0)

淮安A

#include <stdio.h>

int main() {
    int n = 0, num = 0;
    int arr[300] = {0};
    while (scanf("%d", &n) != EOF) {
        for (int i = 2; i <= n; i++) {
            arr[i] = i;
        }
    }
    for (int i = 2; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            if (arr[i] && j % arr[i] == 0) {
                arr[j] = 0;
            }
        }
    }
    for (int i = 2; i <= n; i++) {
        if (arr[i] != 0) {
            printf("%d ", arr[i]);
            num++;
        }
    }
    printf("\n");
    printf("%d\n", n - num - 1);
    return 0;
}

发表于 2023-03-14 10:22:21 回复(0)

WangCL0237

#include<stdio.h>
#include<math.h>
int main(){
    int n = 0,cur = 0,count = 0;
    while(scanf("%d",&n)!=EOF){
        getchar();
        for(int i = 2;i <= n;i++){
            for(int j = 2;j <= sqrt(i);j++){
                if(0 == i % j){
                    cur = -1;
                    break;
                }
            }
            if(cur == 0){
                count++;
                printf("%d ",i);            
            }
            cur = 0;
        }
        printf("\n%d\n",n - count - 1);
        count = 0;
    }
    return 0;
}

发表于 2022-08-04 10:20:58 回复(0)

努力成为码农1

#include<stdio.h>

int main()

{

int n=0;

scanf("%d",&n);

int arr[n];

int i=0;

for(i=2;i<=n;i++)

{

arr[i-2]=i;

}

int j=0;

for(i=0;i<n-1;i++)

{

for(j=2;j<arr[i];j++)

{

if((arr[i]%j)==0)

{

arr[i]=0;

}

int count=0;

for(i=0;i<n-1;i++)

{

if(arr[i]!=0)

{

printf("%d ",arr[i]);

}

else {

count++;

}

printf("\n");

printf("%d",count);

return 0;

}

发表于 2025-12-01 17:14:11 回复(0)

月十三

n=int(input())
l=[]
count=0
for i in range(2,n+1):
    flag=1
    for j in range(2,i//2+1):
        if i%j==0:
            flag=0
            break
    if flag==1:
        print(i,end=" ")
        count+=1
print()
print(n-count-1)

发表于 2025-11-24 23:10:16 回复(0)

Jance_L

#include <iostream>
using namespace std;

int main() {
    int n;
    int cnt=0;
    cin>>n;
    int a[n];
    for(int i=2;i<n;i++){
        a[i]=i;
    }
    for(int i=2;i<n;i++){
        for(int j=i+1;j<n;j++){
            if(a[j]%i==0){
                a[j]=0;
            }
        }
    }
    int sum =0;
    for(int i=2;i<n;i++){
        if(a[i]!=0) {
            cout<<a[i]<<' ';
            cnt++;
        }
    }
    cout<<endl<<n-1-cnt;
   
}
// 64 位输出请用 printf("%lld")

发表于 2025-10-29 16:40:03 回复(0)

牛客618310257号

#include <stdio.h>

int main() {

int a, b[1000]={},c,d;

while(scanf("%d",&a)!=EOF){

int i=0;

for(c=2;c<=a;c++){

int m=0;

for(d=2;d<c;d++){

if(c%d==0){

m++;

i++;

break;

}

if(m==0){

printf("%d ",c);

}

printf("\n");

printf("%d",i);

}

return 0;

}

发表于 2025-08-09 00:02:27 回复(0)

提交观点

问题信息

上传者：牛客309119号

难度：

138条回答 384收藏 3691浏览

通过挑战的用户

查看代码

你丫三条

2023-03-09 17:09:49
王津

2022-12-05 19:15:13
拒绝pua的小...

2022-11-03 20:36:04
小写H

2022-09-25 15:34:06
牛客13979...

2022-09-15 17:11:53

筛选法求素数

输入描述:

输出描述:

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题