Prime Number
Time Limit : 1 sec, Memory Limit : 65536 KB
Prime Number
Write a program which reads an integer n and prints the number of prime numbers which are less than or equal to n. A prime number is a natural number which has exactly two distinct natural number divisors: 1 and itself. For example, the first four prime numbers are: 2, 3, 5, 7.
Input
Input consists of several datasets. Each dataset has an integer n (n ≤ 999999) in a line.
The number of datasets ≤ 30.
Output
For each dataset, prints the number of prime numbers.
Sample Input
10 3 11
Output for the Sample Input
4 2 5
题意:
输出 N (<= 999999)以内素数的个数。
思路:
素数筛选法。
AC:
#include <stdio.h> #include <string.h> #define MAX 1000000 int pri[MAX]; void make_pri() { memset(pri,0,sizeof(pri)); for(int i = 2;i < MAX;i++) { if(pri[i]) continue; for(int j = i + i;j < MAX;j += i) pri[j] = 1; } } int main() { int n; make_pri(); while(~scanf("%d",&n)) { int sum = 0; for(int i = 2;i <= n;i++) if(!pri[i]) sum++; printf("%d\n",sum); } return 0; }
相关推荐
PrimeNumber 素数生成器 V7.0.0.0 18.7 KB 可快速生成指定范围内的所有素数,并可格式化输出;还可对单个自然数快速因数分解。 HugeCalc V6.x 以上版本现已提供该程序相应导出接口,欢迎使用。 若借助算法库 ...
PrimeNumber 素数生成器 V6.0.0.3 18.4KB 可快速生成指定范围内的所有素数,并可格式化输出;还可对单个自然数快速因数分解。 HugeCalc V6.x 以上版本现已提供该程序相应导出接口,欢迎使用。 若借助算法库 ...
primenumber找质数代码
经典算法,求素数(PrimeNumber),使用C#实现
java代码-使用java解决输出1000以内最大的n个质数及其和。输出形式“质数1+质数2+...+质数n=的源代码 ——学习参考资料:仅用于个人学习使用!
资源名:MATLAB寻找素数的源程序代码_prime_number_素数_素数寻找_matlab 资源类型:matlab项目全套源码 源码说明: 全部项目源码都是经过测试校正后百分百成功运行的,如果您下载后不能运行可联系我进行指导或者...
任何一个偶数都等于二个素数之差,徐万东,,本文构筑了奇数差式堆垒,并利用奇合数对奇数差式堆垒进行二维筛选,剩下的是二个奇素数之差式。然后,我们利用第二数学归纳法证
最快的素数筛法, 3秒初始化后在P4上能算出2^31 以内素数个数,之后10ms内算出任意 0-2^31之间素数个数 (为节省99%的存贮时间而不存贮).
pi+素数.py
输入一个数字,判断该数字是否为素数,并弹出信息
Python 编写的质数运算算法,使用开方运算原理,实现较快速求解
这个程序是教大家如何编写一定数量素数的程序,当然如果想编写一定数量的素数 要 加上 import java.until.*; 加入输入语句 输入 范围就可以了
圆位置判定+质数判定+整根式化简三个功能,VB做得。。本人是新手,所以技术可能不太过关,偶尔会有出错的时候,希望高手帮忙优化下,谢谢!
求素数的程序,用了一些标准库.不难,但很有用
随机数+素数。随机生成n个数,并以列表形式输出,再输出其中的素数。.py
编制具有如下原型的函数prime,用来判断整数n是否为素数:bool prime(int n); 而后编制主函数,任意输入一个大于4的偶数d,找出满足d=d1+d2的所有数对,其中要求d1与d2均为素数(通过调用prime来判断素数)。如偶数...
输出给定数值范围内的所有素数。 使用链表保存数据,动态内存分配,并采用递归思想搜索
三-素数问题 6 素数性质 6 素数猜想 6 素数测试 6 筛素数 7 区间筛素数 7 大素数测试 7 素因子相关 8 梅森素数 8 筛可以表示成x^2+(x+1)^2的素数 9 高斯整数环与高斯素数 10 n!中素数y的个数 10 筛1~n的因子个数O(n)...
而后编制主函数,任意输入一个大于4的偶数d,找出满足d=d1+d2的所有数对,其中要求d1与d2均为素数(通过调用prime来判断素数)。如偶数18可以分解为11+7以及13+5;而偶数80可以分解为:43+37、61+19、67+13、73+7。...
素数(prime number)又称质数,有无限个。除了1和它本身外,不能被其他自然数整除。换句话说就是该数除了1和它本身以外不再有其他的因数的数。 注意:最小的素数是2。 话不多说,上代码! prime=[] #用一个列表来存储...