首页 > 试题广场 >

筛选法求素数

[编程题]筛选法求素数

热度指数：30764 时间限制：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

算法知识视频讲解

鲸鱼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)

牛客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)

冬眠狗

#include <stdio.h>

int main() {
	int n = 0;

	scanf("%d", &n);
	int arr[100] = { 0 };
	for (int i = 0;i < n - 1;i++)
	{
		static int j = 2;
		if (j <= n)
		{

			arr[i] = j;
			j++;

		}
		else {
			break;
		}
	}
	int count = 0;
	for (int k = 0;k < n - 1;k++)
	{
		if (arr[k] != 0)
		{
			for (int l = k + 1;l < n - 1;l++)
			{
				if ((arr[l] % arr[k] == 0) && arr[l] != 0)
				{
					arr[l] = 0;
					count++;
				}
			}

		}
		
	}
	for (int c = 0;c < n - 1;c++)
	{
		if (arr[c] != 0)
		{
			printf("%d ", arr[c]);
		}
	}
	printf("\n");
	printf("%d", count);
	return 0;
}

发表于 2025-06-19 22:29:29 回复(0)

XsirZNB

#include <stdio.h>

int main() {

int a, count = 0;

scanf("%d\n", &a);

int arr[a - 1];

for(int i = 0; i < a - 1; i++)

{

arr[i] = i + 2;

for(int j = 0; j < i; j++)

{

if(!arr[j])

continue;

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

{

arr[i] = 0;

count++;

break;

}

if(arr[i])

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

}

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

return 0;

}

发表于 2025-04-28 23:31:35 回复(0)

相里墨瞳

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

发表于 2025-01-09 15:00:39 回复(0)

会编程的小鱼干喜欢摸鱼

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

发表于 2024-12-31 09:46:09 回复(0)

起床了的花生米很糊涂

#include <stdio.h>

int main() {

int n,i,j,count=0,a[100];

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

{

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

{

a[i]=i;

}

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

{

for(j=1+i;j<=n;j++)

{

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

a[j]=0;

}

if(n>=3)

{

a[1]=1;a[2]=2;

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

{

if(a[i]==0)

count++;

if(a[i]!=0)

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

}

printf("\n");

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

}

return 0;

}

发表于 2024-09-21 23:31:09 回复(0)

Anout

试除开平方法

一个非素数可以拆成两个数相乘，这两个数的其中一个一定小于等于这个非素数的开平方

#include <stdio.h>
#include <math.h>

int main() {
    int n, num = 0;
    scanf("%d", &n);
    int i = 0, j = 0;
    for (i = 2; i <= n; i++) {
        for (j = 2; j <= sqrt(i); j++) {
            if (i % j == 0) break;
        }
        if (j > sqrt(i)) {
            printf("%d ", i);
            num++;
        }
    }
    printf("\n%d", n - num - 1);

    return 0;
}

发表于 2024-08-23 11:19:12 回复(0)

寻职seeker

//通过在向数组输入数据的过程中，进行是否为素数判断，保证数组(素数位)输入的是0
#include <stdio.h>

//函数：判断i是否位素数
int chick(int i){
    for (int j = 2; j < i; j++) {
        if (i%j == 0) {
            return 1;
        }
    }
    return 0;
}
int main() {
    int n, count = 0;
    scanf("%d",&n);
    int a[n];
    //向数组中写入数据，同时调用chick()判断需要输入0的位置
    for (int i = 2; i <= n; i++) {
        if (chick(i)) {
            a[i] = 0;
            count++;
        }else {
            a[i] = i;
        }
    }
    //输出
    for (int i = 2; i <= n; i++) {
        if (a[i] == i) {
            printf("%d ",i);
        }
    }
    printf("\n%d",count);
    return 0;
}

发表于 2024-08-17 16:56:46 回复(0)

亓伟歌

#include <stdio.h>

int main() {
    int n = 0;
    while(scanf("%d", &n) != EOF)
    {
        int count = 0;
        for (int i = 2; i < n; i++)
        {
            int m = 0;
            for (int j = 2; j < i; j++)
            {
                if(i % j == 0) 
                {
                    count++;
                    m++;
                    break;
                }

            }
            if(m==0)
            {
                printf("%d ", i);
            }
        }
        printf("\n%d ", count + 1);
    }
    return 0;
}

发表于 2024-08-10 15:13:23 回复(0)

__Forever__

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

bool IsPrime(int n)
{
    int flag = 0;
    //2是特殊的一个素数
    for(int i = 2; i < n - 1; i++)
    {
        if(n % i == 0 && n != 2)
        {
            flag++;
            break;
        }
    }
    return flag == 0;
}

void Distincy(int n)
{
    int count =0;
    for(int i = 2; i <= n; i++)
    {
        //a[i]不是素数，或者不是
        int tmp = i;
        if(!IsPrime(tmp))
        {    
            tmp = 0;
            count++;
        }
        //不是素数已经为0，不为零的是素数
        if(tmp != 0)
            printf("%d ", tmp);
    }
    printf("\n");
    printf("%d", count);
}

int main() 
{
    int n;
    scanf("%d", &n);
    Distincy(n);
    return 0;
}

发表于 2024-06-28 22:52:30 回复(0)

想奋斗的烤冷面在okr拆解

#include<stdio.h>

#include<math.h>

int main()

{

int n=0;

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

{

int arr[100]={0};

int y=0;

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

{

int flag=0;

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

{

if(i%j==0)

{

flag=1;

break;

}

if(flag==0)

{

arr[y]=i;

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

y++;

}

printf("\n");

printf("%d\n",n-(y+1));

}

return 0;

}

发表于 2024-04-13 15:10:20 回复(0)

徐文达

#include <stdio.h>
#include <math.h>

int main() 
{
    int n = 0;
    int i = 0;
    int j = 0;
    int flag = 0;
    int count = 0;

    while (scanf("%d", &n) != EOF) 
    {
        for(i = 2; i <= n; i++)
        {
            flag = 1;

            for(j = 2; j <= sqrt(i); j++)
            {
                //不是素数
                if(i % j == 0)
                {
                    flag = 0;
                }
            }
            //是素数
            if(flag)
            {
                printf("%d ", i);
                count++;
            }
        }
        //不是素数的数量
        printf("\n%d\n", n - count - 1);//从2清零开始，所以要-1
    }
    return 0;
}

编辑于 2024-03-19 14:23:13 回复(0)

yangwy

#include <stdio.h>

int main() {
    int n;
    scanf("%d", &n);
    int arr[n+1];
    for(int i=2; i<=n; i++){
        arr[i]=i;
    }
    //输入
    int sum=0;
    printf("2 3 5 7 ");
    for(int i=2; i<=n; i++){
        if(arr[i]%2 == 0){
            arr[i] = 0;
            sum++;
        }else if(arr[i]%3 == 0){
            arr[i] = 0;
            sum++;
        }else if(arr[i]%5 == 0){
            arr[i] = 0;
            sum++;
        }else if(arr[i]%7 == 0){
            arr[i] = 0;
            sum++;
        }else{
            printf("%d ", arr[i]);
        }
    }
    printf("\n%d\n", sum-4);
    return 0;
}

编辑于 2024-01-31 17:21:14 回复(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)

RWERWDF

#include <stdio.h>

int main()
{
    int n = 0;
    int i,j=0;
    int count=0;
    while(scanf("%d",&n)!=EOF)
    {
        for(i = 2;i<n;i++)
        {
            for(j = 2;j<i;j++)
            {
                if(i%j==0)
                {
                    break;
                }
            }
            if(i==j)
            {
                printf("%d ",i);
                count++;
            }
        }
        //减掉1因为只算二之后的
        printf("\n%d",n-count-1);
    }
    return 0;
}

发表于 2023-11-18 23:07:00 回复(0)

算命的春茶

#include <stdio.h>
int main()
{
    int n;
    while(scanf("%d\n",&n) != EOF)
    {
        int i,pm;
        int arr[n];
        for(i=0;i<n;i++)
        {
            arr[i] = i+1;//将1~n之间的数赋值给arr
        }
        int count = 0;
        for(i=2;i<n;i++)
        {
            int j;
            for(j=i;j<n;j++)
            {
                if(i != 0&&arr[j]%i == 0)//拿i%j，整除的就赋值为零
                {
                    arr[j] = 0;
                }
            }
            if(arr[i] == 0)//如果arr[i]被赋值为零，个数加一
            {
                count++;
            }
        }
        for(i=1;i<n;i++)//打印二及其之后的数
        {
            if(arr[i] != 0)//取其不为零的数
            {
                printf("%d ",arr[i]);
            }
        }
        printf("\n%d",count);//先换行再打印
    }
    return 0;
}

发表于 2023-11-08 09:40:09 回复(0)

秃驴应该痛

#include <stdio.h>

int is_prime(int x)

{

for(int i=2;i*i<=x;i++)

{

if(x%i==0)

{

return 0;

}

return 1;

}

int main()

{

int n;

int count=0;//2后被清除的数的个数

int arr[100];

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

{

int k=0;

for(int i=2;i<=n;i++)//打印素数组

{

int ret=is_prime(i);

if(ret==1)

{

printf("%d ",i);

arr[k]=i;

k++;

count++;

}

printf("\n%d",n-count-1);//注意2是素数但是没有被清零

}

return 0;

}

发表于 2023-04-11 00:47:44 回复(0)

提交观点

问题信息

上传者：牛客309119号

难度：

61条回答 386收藏 3855浏览

通过挑战的用户

查看代码

你丫三条

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

筛选法求素数

输入描述:

输出描述:

输入

输出

试除开平方法

问题信息

热门推荐

通过挑战的用户

相关试题