首页 > 试题广场 >

筛选法求素数

[编程题]筛选法求素数
  • 热度指数：29445 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
用筛选法求n以内的素数。筛选法求解过程为：将2~n之间的正整数放在数组内存储，将数组中2之后的所有能被2整除的数清0，再将3之后的所有能被3整除的数清0 ，以此类推，直到n为止。数组中不为0 的数即为素数。

输入描述:
多组输入，每行输入一个正整数（不大于100）。


输出描述:
针对每行输入的整数n，输出两行，第一行，输出n之内（包括n）的素数，用空格分隔，

第二行，输出数组中2之后被清0 的个数。每行输出后换行。
示例1

输入

20

输出

2 3 5 7 11 13 17 19
11
算法知识视频讲解
添加回答
C
鲸鱼lord头像 鲸鱼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)
C
牛客618310257号头像 牛客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)
C
冬眠狗头像 冬眠狗 
#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)
C
XsirZNB头像 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)
C
相里墨瞳头像 相里墨瞳 
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)
C
会编程的小鱼干喜欢摸鱼头像 会编程的小鱼干喜欢摸鱼 
#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)
C
起床了的花生米很糊涂头像 起床了的花生米很糊涂
#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)
C
Anout头像 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)
C
寻职seeker头像 寻职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)
C
亓伟歌头像 亓伟歌 
#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)
C
__Forever__头像 __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)
C
想奋斗的烤冷面在okr拆解头像 想奋斗的烤冷面在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)
C
徐文达头像 徐文达 
#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)
C
yangwy头像 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)
C
诗奕头像 诗奕 
#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)
C
RWERWDF头像 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)
C
算命的春茶头像 算命的春茶 
#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)
C
秃驴应该痛头像 秃驴应该痛
#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条回答 3263浏览

热门推荐

通过挑战的用户

查看代码

相关试题

筛选法求素数

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号