首页 > 试题广场 >

筛选法求素数

[编程题]筛选法求素数
  • 热度指数：27095 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
用筛选法求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
算法知识视频讲解
添加回答
美美哒蔡蔡子头像 美美哒蔡蔡子
#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++
virteki73头像 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)
C
阿金要努力头像 阿金要努力 
#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)
C
敲码挣钱头像 敲码挣钱 
#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)
C
牛客688983736号头像 牛客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头像 时影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)
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
时不语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)
C
淮安A头像 淮安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)
C
WangCL0237头像 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)
喜欢飞来飞去的卷王在学c语言头像 喜欢飞来飞去的卷王在学c语言 
#include <stdio.h>

int main() {
   int n,count=0;
   while(scanf("%d",&n)!=EOF)
   {
     int array[n];
     int i,j;
     for(i=1,j=2;i<n&&j<n;j++,i++) //有个坑，输入数字为2~n，一开始写i=0开始导致数据存到array[0]~array[n-2]位置，
//array[n-1]被置0，输出清0个数多1
     {
        array[i]=j;
     }
     for(i=1;i<n;i++)
     {
        if(array[i]!=0)        //必须有这个，不然会发生(报错)当i为0为除数的情况
        {
        for(j=i+1;j<n;j++)
        {
            if(array[j]%array[i]==0) //中规中矩的求质数
            {
                array[j]=0;          //一开始错误的在后面count++
            }
        }
        } 
     }
     for(i=1;i<n;i++)
     {  
       if(array[i]!=0)
        {
            printf("%d ",array[i]);
        }
        else{
            count++;
        }
     }
     if(n<=2)            //没有什么用，就是让结构更清晰
     {
        count=0;
     }
     printf("\n");
     printf("%d",count);
   } 
    return 0;
}

发表于 2024-10-02 10:06:41 回复(0)
Python3
45度信仰头像 45度信仰 
n = int(input())
arr = (i for i in range(2,n+1))
def func(arr):
    counts = 0
    char = ''
    for i in arr:
        flage = 1
        med = int(pow(i,0.5))
        for j in range(2,med+1):
            if i%j == 0:
                flage=0
                break
        if flage:
            char+=" "+ str(i)
        else:
            counts += 1
    print(' '.join(char.split()))
    print(counts)           
func(arr)

发表于 2024-09-28 00:32:48 回复(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)
Java
Wilburlee头像 Wilburlee 
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int n = in.nextInt();
            int count = 0;
            for (int i = 2; i <= n; i++) {
                if (prime(i) == 1) {
                    System.out.print(i + " ");
                } else {
                    count++;
                }
            }
            System.out.println();
            System.out.println(count);
        }
    }
    public static int prime(int i) {
        for (int j = 2; j < i; j++) {
            if (i % j == 0) {
                return 0;
            }
        }
        return 1;
    }
}

发表于 2024-09-04 12:57:14 回复(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)
提交观点

问题信息

上传者：牛客309119号
难度：
126条回答 2666浏览

热门推荐

通过挑战的用户

查看代码

相关试题

筛选法求素数

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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