首页 > 试题广场 >

筛选法求素数

[编程题]筛选法求素数
  • 热度指数：28871 时间限制：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
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)
C
牛客980361244号头像 牛客980361244号 
#include <stdio.h>
int main(){
    int n, i, j, cnt;

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

    return 0;
}


发表于 2023-04-08 19:03:13 回复(0)
C
时不语ac头像 时不语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)
提交观点

问题信息

上传者：牛客309119号
难度：
58条回答 3015浏览

热门推荐

通过挑战的用户

查看代码

相关试题

筛选法求素数

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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