`

java经典算法(一)求100以内的素数

 
阅读更多

一、用筛选法

所谓的筛选法:是指从小到大筛去已知的一个素数的所有倍数,根据2我们可以筛去“4,6,8,...,100”等数,然后根据3可以筛去“9,15,...,99”等数,注意此时的6,12早就被作为2的倍数给筛去了,由于4已经被筛去了,所以下一个筛选数是5

编程原理:定义一个大小为101的数组,把被筛去的数赋值为1,留下未被筛去的并且数组下标大于等于2的数输出,输出的就是质数。

实例:

package rmd_lygp_front.test;

public class Test {
	
	public static void main(String[] args) {
		 int[] a = new int[101];  
	        int i, j = 2;  
	          
	        while (j < 101) {  
	            if (a[j] == 0) {  
	                for (i = j + 1; i < 101; i++) {  
	                    if (i % j == 0) {  
	                        a[i] = 1;  
	                    }  
	                }  
	            }  
	            j++;  
	        }  
	          
	        for (int k = 0; k < 101; k++) {  
	            if (k >= 2 && a[k] == 0) {  
	                System.out.println(k);  
	            }  
	        }  
	}

}

二、普通方法:

证明:使用k = (INT)Math.sqrt(i)来控制循环的可靠性,通过举例来证明当i=8时,他的值介于2的平方和3的平方之间,所以当4<i<9时,k=(INT)Math.sqrt(i) = 2; 3*2< 8 < 3*3 ,所以如果8能够被一个数整除的话就应该小于3大于1的整数,i=40的时候 40<7*7 ,所以只要40不能被大于1小于等于7的数整除,就可以断定40不是质数

实例:

package rmd_lygp_front.test;

public class Test {
	
	public static void main(String[] args) {
		int i, j, k;  
        for (i = 2; i < 100; i++) {  
            k = (int) Math.sqrt(i);  
            for (j = 2; j <= k; j++) {  
  
                if (i % j == 0)  
                    break;  
  
            }  
            if (j > k) {  
                System.out.println(i + " ");  
            }  
        }  
	}
}

分享到:
评论

相关推荐

    Java:打印出100以内的质数

    以下是一个简单的Java程序,用于打印100以内的质数: ```java public class PrimeNumbers { public static void main(String[] args) { int limit = 100; System.out.println("100以内的质数有:"); for (int...

    [Java算法练习]-求100以内的素数.java

    [Java算法练习]-求100以内的素数.java

    Java求100之内的素数.rar

    本示例中,我们探讨的主题是如何使用Java编程语言来找出100之内的所有素数。素数是自然数中的一个特殊类别,它们只能被1和自身整除,没有其他正因数。在数学上,2是最小的素数,而1则不被认为是素数。 在Java中,...

    java打印100以内的素数

    Java打印100以内的素数是一个常见的编程练习,它涉及到基础的算法设计和Java编程技巧。素数是大于1的自然数,除了1和它自身外,不能被其他自然数整除的数。在Java中,我们可以通过一系列步骤来实现这个功能。 首先...

    求100以内的素数

    #### 三、求解100以内素数的算法实现 - **核心思路**: - 对于每个数`i`(从2到100),检查其是否为素数。 - 使用一个变量`jishu`记录是否找到因子,初始值设为1表示当前数可能是素数。 - 计算每个数的平方根`...

    Java面试经典算法

    Java面试经典算法 Java 面试经典算法是指在 Java 面试中经常会被问到的算法题目,这些题目涵盖了数据结构、算法设计、编程语言基础知识等方面的知识。本文总结了 17 道 Java 面试经典算法题目,并对每道题目进行了...

    Java求100以内的所有素数并输出

    本示例中,我们将探讨如何使用Java语言找出100以内的所有素数并将其输出。这个任务通常被用作教学示例,帮助初学者理解循环、条件判断以及算法设计。 首先,我们需要一个方法来检查一个数是否为素数。这个方法通常...

    100以内的素数

    100以内的素数的JAVA的算法

    java求100以内的素数示例分享

    通过本文的介绍,读者不仅学会了如何用Java语言编写找出100以内素数的程序,还对程序优化有了初步的了解。实际上,算法的效率问题往往牵涉到更深层次的计算理论知识,而如何设计更优的算法,不仅是一个技术问题,也...

    Java用面向对象和面向过程方法解求100内素数并输出素数之和

    在给定的文件中,通过两种不同的编程范式——面向对象和面向过程,来解决一个经典问题:找出100以内的所有素数,并计算这些素数的总和。这不仅是一次对数学原理的应用,也是对编程语言特性和设计模式的深度探讨。 #...

    JAVA经典算法32题

    以下是一些基于给定题目所涉及的Java算法知识点: 1. **斐波那契数列**:程序1展示了斐波那契数列的实现,其中`f(x)`函数使用递归方法计算第`x`个月的兔子数量。斐波那契数列的规律是每个数等于前两个数的和。递归...

    java使用筛选法求n以内的素数示例(java求素数)

    以下是一个使用筛选法在Java中求解n以内素数的示例代码: ```java public class AratosternyAlgorithm { public static void getPrimes(int n) { if (n || n &gt; 1000000) { throw new IllegalArgumentException(...

    打印出100以内的质数Java

    Java作为一种广泛使用的编程语言,提供了多种方法来找出100以内的所有质数。以下将详细介绍如何使用Java实现这个功能,并探讨相关的编程概念。 1. **基础概念** - **循环**:在Java中,`for`循环是常用的结构,...

    java代码-计算1亿以内素数

    在这个"java代码-计算1亿以内素数"的项目中,我们将深入探讨如何用Java编写程序来高效地找出1亿以内所有的素数。 首先,我们要理解什么是素数。素数是大于1且除了1和它自身外没有其他正因数的自然数。例如,2、3、5...

    算法:百钱买百鸡&100;以内质数和

    简单的算法问题:百钱买百鸡以及100以内质数和,java语言实现

    java实现计算1亿以内的素数

    ******************计算一亿以内的素数********************* 素数总数:XXXXX个 计算过程的时间:XXXXX秒 写入文本时间:XXXX秒 执行程序总时间:XXXX秒 ********************************************************...

    求素数的Java表示

    java的10000以内的数的素数的求法,算法简单易懂

    java程序求素数和并输出结果

    本次探讨的主题是“Java程序求10000以内素数和并输出结果”。这不仅是一个基础的编程实践,同时也是对Java语言特性、循环结构、条件判断以及数组操作等多方面技能的综合运用。下面,我们将深入解析这一知识点,包括...

    Prime.java 计算一亿以内素数的个数

    暴力法 | 暴力法优化(取中间数)|暴力法优化(取平方根)|埃氏筛法|未知算法。五种算法的效率依次递增。在同一个Prime.java文件中都可以测试。

    JAVA算法题目集合程序习题:

    【JAVA算法题目集合程序习题】是一系列针对Java编程者设计的练习,旨在提升编程思维能力和代码编写技巧。这些题目涵盖了基础、深入和综合三种难度级别,覆盖了数学、逻辑和数据结构等多个方面。 1. **基础题**: -...

Global site tag (gtag.js) - Google Analytics