C 教程

C 练习实例36 - 求100之内的素数

题目：求100之内的素数。

程序分析：质数（prime number）又称素数，有无限个。一个大于1的自然数，除了1和它本身外，不能被其他自然数整除。

程序源代码：

实例

// Created by www.runoob.com on 15/11/9. // Copyright © 2015年菜鸟教程. All rights reserved. // #include<stdio.h> #include<math.h> int main() { int i,j,k,n=0; for(i=2;i<=100;i++) { k=(int)sqrt(i); for(j=2;j<=k;j++) if(i%j==0) break; if(j>k) { printf("%d ",i); n++; if(n%5==0) printf("\n"); } } return 0; }

以上实例输出结果为：

2 3 5 7 11 
13 17 19 23 29 
31 37 41 43 47 
53 59 61 67 71 
73 79 83 89 97

C 语言经典100例

C 练习实例35 – 字符串反转

C 练习实例37 – 排序

3 篇笔记写笔记

参考方案：

#include <stdio.h>
#include <math.h>
#include <stdbool.h>
#include <stdlib.h>
#include <sys/time.h>

//素数判定 筛选法
int main(){
    int num = 100;
    int i, j;
    //scanf("%d", &num);
    //getchar();
    bool *b;
    b=(bool *)calloc(num + 1, sizeof(bool));
    b[0] = false;
    for(i = 1; i <= num; i++){
        if(i % 2 == 0){
           b[i] = false;
        }else{
           b[i] = true;
        }
    }

    for(int i = 3; i <= sqrt(num); i+=2){
        if(b[i]){
            for(j=i+i; j <= num; j+=i)
                b[j] = false;
        }
    }

    
    //输出素数
    printf("2,");    
    for(i = 3; i <= num; i+=2){
       if(b[i]){
           printf("%d,", i);
       }
    }

    free(b);
    b=NULL;
    return 0;
}

红途3年前 (2017-04-26)

参考方法：

//使用数组存储已经获得的素数，使用该数组做为底，当取值范围较大时可有效减少运算量
#include<stdio.h> 

int main()
{
    int i,j,k=0,n;    //k为素数数组的下标
    int prime[1000];   //建立一个素数数组
    printf("请输入求素数值的范围(0-1000):\n");
    scanf("%d",&n);
    prime[0]=2;       //给第一个数组元素赋值
    for(i=2;i<=n;i++)
    {
        for(j=0;j<=k;j++)  
        {
            if(i%prime[j]==0) //求余比较只要对当前的素数数组求余即可
                break;
        }
        if(j>k)
        {
            k++;                //判断i是否为素数，如果是，将其加入数组，下标k加一
            prime[k]=i;
        }   
    } 
    for(i=0;i<=k;i++) 
        printf("%d  ",prime[i]);
}

内拉小付1年前 (2018-11-15)

参考方法：

#include <stdio.h>
#define N 101

int prime[N],pNum=0;
int p[N]={0};   //0表示为素数，1表示为非素数

void Find_Prime(){
    int i,j;
    for(i=2;i<N;i++){
        if(p[i]==0){
            prime[pNum++]=i;
            //埃氏筛法
            for(j=i+i;j<N;j+=i)
                p[j]=1;
        }
    }
}

int main(){
    Find_Prime();
    int i;
    for(i=0;i<pNum;i++){
        printf("%d ",prime[i]);
    }
    return 0;
}

ronnyz12个月前 (03-22)