求素数

た入场券 2022-08-10 04:58 177阅读 0赞

## 求素数 ##

##### Time Limit: 100ms Memory limit: 65536K 有疑问？点这里^\_^ #####

## 题目描述 ##

求小于n的所有素数的数量。

## 输入 ##

多组输入，输入整数n(n<1000000），以0结束。

## 输出 ##

输出n以内所有素数的个数。

## 示例输入 ##

10
    0

## 示例输出 ##

4

## 提示 ##

## 来源 ##

zp

## 示例程序 ##

#include <stdio.h>     
    #include <math.h>     
        
    #define SIZE 1000000     
        
    int Prime[SIZE];    
        
    void JudgePrime();      
        
    int main()    
    {    
        int n;    
        int i;    
        int sum;    
        
        JudgePrime();  
        
        while (scanf("%d", &n))    
        {    
            if (n == 0)    
            {    
                break;    
            }    
        
            if (n <= 2)    
            {    
                printf("0\n");    
                continue;    
            }    
        
            sum = 0;    
            for (i=2; i<n; i++)    
            {    
                if (Prime[i] == 1)    
                {    
                    sum++;    
             }    
            }    
            printf("%d\n", sum);    
        }    
        return 0;    
    }    
        
    void JudgePrime()    
    {    
        Prime[0] = 0;    
        Prime[1] = 0;    
        int i, j;    
        for (i=2; i<SIZE; i++)    
        {    
            Prime[i] = 1;    
        }    
        
        for (i=2; i<SIZE; i++)    
        {    
            if (Prime[i] == 1)    
            {    
                for (j=i*2; j<SIZE; j+=i)    
                {    
                    Prime[j] = 0;    
                }    
            }    
        }    
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，177人围观）

还没有评论，来说两句吧...

相关阅读

相关 Python－求素数序列

分享一个大牛的人工智能教程。零基础！通俗易懂！风趣幽默！希望你也加入到人工智能的队伍中来！请点击[http://www.captainbed.net][http_www.cap

刺骨的言语ヽ痛彻心扉/ 2022年12月25日 10:53/ 0 赞/ 142 阅读

相关求素数

求素数 Time Limit: 100ms Memory limit: 65536K 有疑问？点这里^\_^ 题目描述求小于n的所有素数的数量。输入

た入场券/ 2022年08月10日 04:58/ 0 赞/ 178 阅读

相关【C语言】求素数

/ 求素数 / include <stdio.h> int prime(int num) { int i = 2;//素数能被1整除

ゝ一纸荒年。/ 2022年06月12日 05:27/ 0 赞/ 224 阅读

相关求素数（普通+筛选）

一般求解n以内素数的算法。时间复杂度是o(n\sqrt(n)),当n较小时可以用。代码： ![Center][] 当n较大时，一般选用埃氏筛选法，时间复杂度o(n

逃离我推掉我的手/ 2022年06月11日 08:23/ 0 赞/ 227 阅读

相关 c语言求素数

include <stdio.h> include <stdlib.h> / run this program using the conso

妖狐艹你老母/ 2022年06月07日 10:40/ 0 赞/ 259 阅读

相关筛法求素数

用筛法求素数的基本思想是：把从1开始的、某一范围内的正整数从小到大顺序排列， 1不是素数，首先把它筛掉。剩下的数中选择最小的数是素数，然后去掉它的倍数。依次类推，直到筛子为空时

我不是女神ヾ/ 2022年05月12日 14:42/ 0 赞/ 263 阅读

相关 Delphi 求素数

GUI界面： ![2018111711484825.png][] 源代码： unit Unit1; interface

àì夳堔傛蜴生んèń/ 2022年04月16日 05:09/ 0 赞/ 222 阅读

相关筛选法求素数

int vis[1000]; //记录标记 int p[1000]; //存素数 int main() { int n,i

系统管理员/ 2022年03月10日 07:45/ 0 赞/ 308 阅读

相关求素数

\include<stdio.h> \include<math.h> int prime(int m); int main(void) \{ int co

傷城~/ 2021年11月09日 23:46/ 0 赞/ 319 阅读

相关求素数

素数：在大于1的整数中，只能被1和这个数本身整除的数，如2、3、5、7、11。也叫质数。求0-n之间所有的素数。测试用例：20

╰+哭是因爲堅強的太久メ/ 2021年09月15日 05:02/ 0 赞/ 386 阅读