1。自然数是0,1,2……
2。素数是2,3,5……(不包括1的只能背1和它本身整除的自然数)
public class Test
{
/*
* 最普通的算法:
* 打印num以内的素数并返回素数个数
* n、m分别为外、内层循环,i是第几个素数,s是素数个数
*/
public int prime(int num){
int n,m,i=0,s=0;
label1:
for(n=2;n<=num;n++)
{
for(m=2;m<=n/2;m++)
{
if(n%m==0)
continue label1;
}
s++;
i++;
System.out.println("第"+i+"个素数是:"+n);
}
return s;
}
public static void main(String args[]){
Test test = new Test();
int sum = test.prime(1000);
System.out.println("共"+sum+"个素数");
}
}
【1】求10000以内的所有素数。
素数是除了1和它本身之外再不能被其他数整除的自然数。由于找不到一个通项公式来表示所有的素数,所以对于数学家来说,素数一直是一个未解之谜。像著名的 哥德巴赫猜想、孪生素数猜想,几百年来不知吸引了世界上多少优秀的数学家。尽管他们苦心钻研,呕心沥血,但至今仍然未见分晓。
自从有了计算机之后,人们借助于计算机的威力,已经找到了2
216091以内的所有素数。
求素数的方法有很多种,最简单的方法是根据素数的定义来求。对于一个自然数N,用大于1小于N的各个自然数都去除一下N,如果都除不尽,则N为素数,否则N为合数。
但是,如果用素数定义的方法来编制计算机程序,它的效率一定是非常低的,其中有许多地方都值得改进。
第一,对于一个自然数N,只要能被一个非1非自身的数整除,它就肯定不是素数,所以不
必再用其他的数去除。
第二,对于N来说,只需用小于N的素数去除就可以了。例如,如果N能被15整除,实际
上就能被3和5整除,如果N不能被3和5整除,那么N也决不会被15整除。
第三,对于N来说,不必用从2到N一1的所有素数去除,只需用小于等于√N(根号N)的所有素数去除就可以了。这一点可以用反证法来证明:
如果N是合数,则一定存在大于1小于N的整数d1和d2,使得N=d1×d2。
如果d1和d2均大于√N,则有:N=d1×d2>√N×√N=N。
而这是不可能的,所以,d1和d2中必有一个小于或等于√N。
基于上述分析,设计算法如下:
(1)用2,3,5,7逐个试除N的方法求出100以内的所有素数。
(2)用100以内的所有素数逐个试除的方法求出10000以内的素数。
首先,将2,3,5,7分别存放在a[1]、a[2]、a[3]、a[4]中,以后每求出一个素数,只要不大于100,就依次存放在A数组中的一个单元 中。当我们求100—10000之间的素数时,可依次用a[1]-a[2]的素数去试除N,这个范围内的素数可以不保存,直接打印。
【2】用筛法求素数。简单介绍一下厄拉多塞筛法。厄拉多塞是一位古希腊数学家,他在寻找素数时,采用了一种与众不同的方法:先将2-N的各数写在纸上:
在2的上面画一个圆圈,然后划去2的其他倍数;第一个既未画圈又没有被划去的数是3,将它画圈,再划去3的其他倍数;现在既未画圈又没有被划去的第一个数 是5,将它画圈,并划去5的其他倍数……依次类推,一直到所有小于或等于N的各数都画了圈或划去为止。这时,表中画了圈的以及未划去的那些数正好就是小于 N的素数。
这很像一面筛子,把满足条件的数留下来,把不满足条件的数筛掉。由于这种方法是厄拉多塞首先发明的,所以,后人就把这种方法称作厄拉多塞筛法。
在计算机中,筛法可以用给数组单元置零的方法来实现。具体来说就是:首先开一个数组:a[i],i=1,2,3,…,同时,令所有的数组元素都等于下标 值,即a[i]=i,当i不是素数时,令a[i]=0 。当输出结果时,只要判断a[i]是否等于零即可,如果a[i]=0,则令i=i+1,检查下一个a[i]。
筛法是计算机程序设计中常用的算法之一。
【3】用6N±1法求素数。任何一个自然数,总可以表示成为如下的形式之一:
6N,6N+1,6N+2,6N+3,6N+4,6N+5 (N=0,1,2,…)
显然,当N≥1时,6N,6N+2,6N+3,6N+4都不是素数,只有形如6N+1和6N+5的自然数有可能是素数。所以,除了2和3之外,所有的素数都可以表示成6N±1的形式(N为自然数)。
根据上述分析,我们可以构造另一面筛子,只对形如6 N±1的自然数进行筛选,这样就可以大大减少筛选的次数,从而进一步提高程序的运行效率和速度。
在程序上,我们可以用一个二重循环实现这一点,外循环i按3的倍数递增,内循环j为0-1的循环,则2(i+j)-1恰好就是形如6N±1的自然数。
分享到:
相关推荐
首先,我们需要了解为什么开方根法能提高求素数的效率。传统的检查素数的方法是试除法,即从2到n-1遍历所有整数,看是否有整除的情况。但随着数字增大,这种方法的计算量迅速增加。开方根法的思路是:如果一个数n...
自定义函数求素数(质数).py
本项目以"C语言求素数"为主题,旨在帮助初学者理解如何利用C语言编写程序来找到一个数列中的素数。 首先,我们要了解C语言的基础语法。C语言是一种结构化的编程语言,它的基本结构包括变量定义、数据类型、控制结构...
【标题】: "本例是一个求素数的C语言代码" 在编程领域,素数是指大于1且除了1和它自身以外没有其他正因数的自然数。C语言是一种广泛用于系统编程、应用编程和嵌入式系统的高级编程语言。在C语言中,编写求素数的...
### Java求素数的经典算法 #### 一、引言 素数是指在大于1的自然数中,除了1和它本身以外不再有其他因数的数。求解素数是计算机科学中的一个经典问题,特别是在密码学等领域有着重要的应用价值。Java作为一门流行...
### 动态规划求素数 #### 背景与目的 在计算机科学与数学领域,素数(或称质数)是指仅能被1和自身整除的大于1的自然数。对于某些应用场景,例如密码学中的RSA算法,需要快速高效地生成或识别大范围内的素数。传统...
在VB(Visual Basic)编程语言中,实现求素数的算法是一项基础且重要的任务。素数是指大于1的自然数,除了1和它自身以外,不能被其他自然数整除的数。例如,2、3、5、7、11等都是素数。下面我们将详细探讨如何使用VB...
在Visual Studio(VS)环境下,使用C#编程语言在窗体中实现求素数的功能是一项常见的练习,旨在帮助开发者熟悉Windows Forms应用开发以及基础的算法实现。素数是指大于1且仅能被1和它自身整除的大于1的自然数。在此...
求素数的C语言版本 求素数的C语言版本 求素数的C语言版本
在Java语言中实现求素数的原根,我们需要以下步骤: 1. **素数判断**:首先需要一个函数来判断输入的数是否为素数。可以采用试除法,从2到这个数的平方根,如果发现有任何能整除的数,那么这个数不是素数。如果没有...
java 求质数实例程序 求质数 源代码 简单易懂
c++关于用C++求素数的源程序
最快求素数的算法,求100000000以下所有素数0.3秒 , 在10000000以下的数中找到664579个素数,耗时53毫秒
Console.WriteLine("请输入数字:"); int x; //输入的数字 x = Convert.ToInt32(Console.ReadLine()); DateTime da = DateTime.Now; 。。。。。
### 线性筛法求素数的原理与实现 #### 一、线性筛法的概念及优势 线性筛法是一种高效的算法,能够在O(n)的时间复杂度内找到所有不大于n的素数。相比于传统的遍历取余判断素数的方法,线性筛法在需要频繁判断素数的...
在易语言中实现Eratosthenes筛选法求质数的源码可能如下: ```易语言 .整数变量 n, i, j .布尔型数组 质数表 (n) .输入 "请输入要找的质数上限:", n 质数表.全部赋值 (.真) i = 2 .循环 (n) .如果 质数表[i] j...
用厄拉多塞法求素数的C源代码
数组筛选法求素数c++编程
这是一个用java编写的控制台程序,可以求一个数是不是质数,并且把这个数按递减顺序求,一直求到1,一次性的显示判断
并行计算求素数个数包括java、OpenMP、MPI、.NET、MFC、Windows Api等方法 并行计算求素数个数包括java、OpenMP、MPI、.NET、MFC、Windows Api等方法