精华内容
下载资源
问答
  • Java 算法面试题 判断质数
  • java之简单的判断素数算法

    千次阅读 2017-08-17 09:27:49
    ...概念:质数(prime number)又称素数,有无限个。一个大于1的自然数,除了1和它本身外,不能被其他自然数整除,换句话说就是该数除了1和它本身以外不再有其他的因数,否则称为合数。 朴素法

    转载自:http://blog.csdn.net/ylyg050518/article/details/48266999

    继续算法之旅。关于素数判定这个问题,也是一个很经典的程序设计题目。

    概念:质数(prime number)又称素数,有无限个。一个大于1的自然数,除了1和它本身外,不能被其他自然数整除,换句话说就是该数除了1和它本身以外不再有其他的因数,否则称为合数

    朴素法

    分析:如果要判定一个数自然数n(n>1)是不是素数,从素数定义出发,首先想到的肯定是采用循环,遍历 2至n-1所有值,逐个与n除,判定是否可以整除,如果存在能够整除的情况,则n不为素数。

    改进方法:脱离单纯程序实现的角度,你会发现可以改进的地方在于遍历的范围,如果略作思考,你会发现n/2到n-1的值是不用遍历的,因为最小的试探除数是2,大于n/2的数肯定不能被整除。进一步思考,遍历的范围还可以继续缩小,其实只需将遍历的上限设置成n的平方根即可。简单分析,假设 n可以被p整除,结果为q ,即q=n/p,如果p大于n的平方根,q必定小于n的平方根,所以只要测试n的平方根以下的数字即可,这样可以进一步提高运算效率。


    以下是代码:

    [java]  view plain  copy
    1. <span style="font-size:14px;">public class Prime {  
    2.     /** 
    3.      * 打印1-100的素数 
    4.      *  
    5.      * @param args 
    6.      */  
    7.     public static void main(String[] args) {  
    8.         for (int i = 1; i <= 100; i++)  
    9.             if (isPrime(i))  
    10.                 System.out.println(i);  
    11.   
    12.     }  
    13.   
    14.     public static boolean isPrime(int num) {  
    15.         if (num == 1)  
    16.             return false;  
    17.         int max = (int) Math.sqrt(num);  
    18.         for (int i = 2; i <= max; i++)  
    19.             if (num % i == 0)  
    20.                 return false;  
    21.         return true;  
    22.     }  
    23. }</span>  

    筛数法

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

    具体做法如下:
    <1> 先将1挖掉(因为1不是素数)。
    <2> 用2去除它后面的各个数,把能被2整除的数挖掉,即把2的倍数挖掉。
    <3> 用3去除它后面的各数,把3的倍数挖掉。
    <4> 分别用4、5…各数作为除数去除这些数以后的各数。(事实上,可以简化,如果需要找1~n范围内素数表,只需进行到除数为n^2(根号n),取其整数即可。例如对1~50,只需进行到将50^2作为除数即可。)

    如上算法可表示为:
    <1> 挖去1;
    <2> 用刚才被挖去的数的下一个数p去除p后面各数,把p的倍数挖掉;
    <3> 检查p是否小于n^2的整数部分(如果n=1000, 则检查p<31?),如果是,则返回(2)继续执行,否则就结束;
    <4> 纸上剩下的数就是素数。


    特别说明:为什么除数的筛选范围只到问题规模N的平方根即可?因为通过分析可以知道,当除数的范围大于这个上限(N的平方根取整)时,所有的要筛选的值都和之前筛选过的重复,继续筛选无效。

    代码如下:

    [java]  view plain  copy
    1. /** 
    2.      * 删选法求素数 
    3.      *  
    4.      * @param N 
    5.      */  
    6.     public static void isPrime2(int N) {  
    7.         int[] flags = new int[N + 1];  
    8.         for (int i = 0; i < N + 1; i++)  
    9.             flags[i] = i;  
    10.         flags[1] = 0;// 排除1,1不为素数  
    11.         int max = (int) Math.sqrt(N);// 设定N的除数的范围,小于N的平方根  
    12.         for (int i = 2; i <=max; i++) {  
    13.             for (int j = i + 1; j <= N; j++) {  
    14.                 //筛选,将N的除数的倍数去掉  
    15.                 if (flags[j] != 0 && flags[j] % i == 0) {  
    16.                     flags[j] = 0;  
    17.                 }  
    18.             }  
    19.         }  
    20.         for (int i = 1; i <= N; i++) {  
    21.             if (flags[i] != 0) {  
    22.                 System.out.println(flags[i]);  
    23.             }  
    24.         }  
    25.   
    26.     }  

    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的自然数进行筛选,这样就可以大大减少筛选的次数,从而进一步提高程序的运行效率和速度。

    实现思路:可以和朴素法判定单个自然数是否为素数结合起来,利用循环递增获取指定范围具备6 N±1特征的数字,利用朴素法来判定数字是否为素数,打印出结果。

    以下是代码

    [java]  view plain  copy
    1. /* 
    2.  * 6N+1法求素数 
    3.  */  
    4.   
    5. public static void isPrime3(int N) {  
    6.     if (N <= 1)  
    7.         System.out.println("此范围无素数");  
    8.     else if (N > 1 && N <= 2)  
    9.         System.out.println(2);  
    10.     else if (N > 2 && N <= 4) {  
    11.         System.out.println(2);  
    12.         System.out.println(3);  
    13.     } else {  
    14.         System.out.println(2);  
    15.         System.out.println(3);  
    16.         int k = 1, pre = 0, next = 0;  
    17.         while (true) {  
    18.             pre = 6 * k - 1;  
    19.             next = 6 * k + 1;  
    20.             if (isPrime1(pre) && pre <= N)  
    21.                 System.out.println(pre);  
    22.             else if (pre > N)  
    23.                 break;  
    24.             if (isPrime1(next) && next <= N)  
    25.                 System.out.println(next);  
    26.             else if (next > N)  
    27.                 break;  
    28.             k++;  
    29.         }  
    30.     }  
    31. }  

    特别说明:以上只给出代码样例,并不能保证代码的权威性,加之作者水平有限,难免有不足之处,还望大家多多包涵。


    展开全文
  • 质数(prime number)又称素数,有无限个。质数定义为在大于1的自然数中,除了1和它本身以外不再有其他因数。也可以理解为:这个数与除1之外小于它的数取余不为0,则这个数为质数。 案例 我们在学习或者面试过程中...

    质数(prime number)又称素数,有无限个。质数定义为在大于1的自然数中,除了1和它本身以外不再有其他因数。也可以理解为:这个数与除1之外小于它的数取余不为0,则这个数为质数。

    案例

    我们在学习或者面试过程中经常会问:输出100以内的所有质数

    那我们简单整理一下思路:
    1. 定义整型变量,i 和 j
    2. 利用for循环的嵌套一个一个判断是否i能否被j整除(i % j == 0)
    3. 如果能被整除,也就是说 i 不是质数
    4. 定义一个标识,( isFlag = true), 如果这个标识没有被改变,这个数就是质数
    5. 输出这个数,然后通过外循环进行判断下一个 i 是不是质数
    
    代码如下:
    public static void main(String[] args) {
        boolean isFlag = true;
        for (int i = 2; i < 100; i++) {
            for (int j = 2; j < i; j++) {
                if (i % j == 0) {
                    isFlag = false;
                }
    
            }
            if (isFlag) {
                System.out.println(i);
            }
            isFlag = true;
        }
    }
    

    【拓展】这种方法对于查找100以内的质数来说还是可以的,但是如果将100改成100000呢?或者更大的数呢?那么这种方式还是否同样好用呢?于是我做了如下尝试,将100改成10000,并在代码中添加时间计数器,看最后程序运行完毕需要的时间是多少。
    demo1:

    public static void main(String[] args) {
        boolean isFlag = true;
        long start = System.currentTimeMillis();//获取系统当前累计毫秒数
        for (int i = 2; i < 100000; i++) {
            for (int j = 2; j < i; j++) {
                if (i % j == 0) {
                    isFlag = false;
                }
    
            }
            if (isFlag) {
                System.out.println(i);
            }
            isFlag = true;
        }
        long end = System.currentTimeMillis();//获取系统当前累计毫秒数
    
        System.out.println("所花费的时间为" + (end - start) + "毫秒");
    }
    

    所花费的时间为13919毫秒。 (可以看到,运行效率就低了很多,当然代码运行效率与硬件也有关)

    那我们该如何优化呢?

    优化一

    可以在if条件里面增加break,当能被整除,则不用继续循环下去了,代码如下:

    public static void main(String[] args) {
        boolean isFlag = true;
        long start = System.currentTimeMillis();//获取系统当前累计毫秒数
        for (int i = 2; i < 100000; i++) {
            for (int j = 2; j < i; j++) {
                if (i % j == 0) {
                    isFlag = false;
                     break; // 优化一 :满足条件跳出循环。只对本身非质数的自然数是有效的
                }
    
            }
            if (isFlag) {
                System.out.println(i);
            }
            isFlag = true;
        }
        long end = System.currentTimeMillis();//获取系统当前累计毫秒数
    
        System.out.println("所花费的时间为" + (end - start) + "毫秒");
    }
    

    所花费的时间为1136毫秒,这个时候就可以看到运行效率快了很多,但这还不是最优解法,可以看一下优化二。

    优化二

    上面我们使用break优化,满足了对本身非质数的自然数的优化,那是不是可以对本身是质数的在做一次优化呢,我们可以使用 Math.sqrt(i) 代码示例:

    public static void main(String[] args) {
        boolean isFlag = true;
        long start = System.currentTimeMillis();//获取系统当前累计毫秒数
        for (int i = 2; i < 100000; i++) {
            //优化二: 对本身是质数的自然数是有效的
            for (int j = 2; j <= Math.sqrt(i); j++) {
                if (i % j == 0) {
                    isFlag = false;
                    break; // 优化一 :满足条件跳出循环。只对本身非质数的自然数是有效的
                }
    
            }
            if (isFlag) {
                System.out.println(i);
            }
            isFlag = true;
        }
        long end = System.currentTimeMillis();//获取系统当前累计毫秒数
    
        System.out.println("所花费的时间为" + (end - start) + "毫秒");
    }
    

    所花费的时间为53毫秒。这就明显快了很多了

    我们也可以做一下其他的优化,如 System.out.println(i) 也是比较消耗性能的,可以将代码注释,替换成累加count:

    public static void main(String[] args) {
            boolean isFlag = true;
            int count = 0;
            long start = System.currentTimeMillis();//获取系统当前累计毫秒数
            for (int i = 2; i < 100000; i++) {
                //优化二: 对本身是质数的自然数是有效的
                for (int j = 2; j <= Math.sqrt(i); j++) {
                    if (i % j == 0) {
                        isFlag = false;
                        break; // 优化一 :满足条件跳出循环。只对本身非质数的自然数是有效的
                    }
    
                }
                if (isFlag) {
                    count++;
    //                System.out.println(i);
                }
                isFlag = true;
            }
            long end = System.currentTimeMillis();//获取系统当前累计毫秒数
    
            System.out.println("100000以内的质数个数为" + count + "个");
            System.out.println("所花费的时间为" + (end - start) + "毫秒");
        }
    

    100000以内的质数个数为9592个
    所花费的时间为12毫秒

    这个时候赶脚自己还要学习的很多呀!!!

    展开全文
  • 判断101-300之间有多少个素数质数),并输出所有素数

    问题描述

           判断101-300之间有多少个素数,并输出所有素数。

    问题分析

           判断素数的方法:用一个数分别去除2到sqrt(这个数),如果不能被整除, 则表明是素数,反之不是素数。

    代码实现

    public class PrimeNumber {
        public static void main(String[] args) {
            int sum = 0;
            for (int i = 101; i < 300; i += 2) {
                boolean flag = true;
                for (int j = 2; j <= Math.sqrt(i); j++) {
                    //如果能被整除则不是素数,跳出内层循环
                    if (i % j == 0) {
                        flag = false;
                        break;
                    }
                }
                //如果是素数,素数个数+1并输出当前的素数
                if (flag) {
                    sum++;
                    System.out.print(i + " ");
                }
            }
            System.out.println();
            //输出总的素数个数
            System.out.println(sum);
        }
    }
    

    运行结果

    101~300之间的素数

    展开全文
  • 在做书上的练习题,判断质数似乎也是一个很经典的题了? 自己做了下然后感觉写得比网上查的简单一点,大概也就少些一个flag吧,感觉查到好多都是定flag…… //javac -encoding utf-8 Testt.java import java.util...

    在做书上的练习题,判断质数似乎也是一个很经典的题了?
    自己做了下然后感觉写得比网上查的简单一点,大概也就少写一个flag吧,感觉查到好多都是定flag……

    //javac -encoding utf-8 Testt.java
    import java.util.Scanner;
    
    public class Testt {
    	public static void main(String[] args) {
    		System.out.println("输入一个数,判断其是否为质数");
    		Scanner sc = new Scanner(System.in);
    		int num = sc.nextInt();
    		
    		for (int i=2; i<num; i++) {
    			if (num%i == 0) {
    				System.out.println(num + "不是质数");
    				break;
    			} else {
    				System.out.println(num + "是质数");
    				break;
    			}
    		}
    	}
    }
    
    • 后来看了眼书后面的参考(《やさしいJava 第7版》高橋麻奈),思路应该是一样的不过她条件反着写,而且感觉直接以else if结尾的写法我不会想到(还是新手被if~else套路固定住了)。
    //javac -encoding utf-8 Testt.java
    import java.util.Scanner;
    
    public class Testt {
    	public static void main(String[] args) {
    		System.out.println("输入一个数,判断其是否为质数");
    		Scanner sc = new Scanner(System.in);
    		int num = sc.nextInt();
    		
    		for (int i=2; i<=num; i++) {
    			if (i == num) {
    				System.out.println(num + "是质数");
    			} else if (num%i == 0) {
    				System.out.println(num + "不是质数");
    				break;
    			}
    		}
    	}
    }
    
    展开全文
  • 题目:素数也就是我们常说的质数,也就是只能被1或者被它自己整除。最小的素数为2。 例如:2,3,7,11,13… 通常我们求素数是这样写的: public static void main(String[] args) { for (int i = 2; i < 100;...
  • //利用Java判断一个数是否是素数算法 boolean f(int a){ boolean ean = true; for(int i=2;i&lt; Math.sqrt(a);i++){ //Math.sqrt 是调用Math类中的sqrt方法,求一个数的平方根 if(a%i==0){ ean = ...
  • 最近刷题刷到了包含判断素数问题的题型,这里写篇博客来分享下! 首先我们来讲下什么是素数 1、素数的概念 素数在数学中我们也叫:质数,两个是一个东西 素数:一个大于1的整数,只能被 1 和 自身 整除的的整数,...
  • java算法--判断质数

    2017-06-05 23:54:10
    java算法判断质数分析:判断素数的方法:用一个数x分别除以 2 到 sqrt(x),如果能被整除, 则表明此数不是素数,反之是素数/** * 判断 101-200 之间有多少个素数,并输出所有素数。 * @author Rain_JN * @data...
  • Java质数的几种常用算法分析

    千次阅读 2019-03-25 14:22:37
    本文实例讲述了Java质数的几种常用算法。分享给大家供大家参考,具体如下: 1、根据质数的定义求 质数定义:只能被1或者自身整除的自然数(不包括1),称为质数。 利用它的定义可以循环判断该数除以比它小的每个...
  • Java判断质数的方法

    千次阅读 2020-08-15 19:48:01
    Java判断质数的几种方法 说明: 1.质数:又称素数。是一个大于1的自然数(最小质数为2)。除了1和它自身外,不能被其他自然数整除的数。 =>质数:用n除[2,n-1]的所有数,不能整除就是n就是质数。 2.[2,n-1]...
  • Java素数算法

    2020-08-12 21:58:10
    质数又称素数。一个大于1的自然数,除了1和它自身外,不能被其他自然数整除的数叫做质数;否则称为合数。 0和1既不是质数也不是合数,最小的质数是2 二、方法介绍 1.最直观,但效率最低的写法 public static ...
  • java算法——质数

    2020-11-17 20:26:09
    判断一个数是不是质数 只需要让这个数 循环 除以2到根号n的数 如果出现整除的现象,则不是质数,反之则为质数 源代码: public static int F(int x) { //判断是否为质数 2,3,5,7,11,13,17,19...... if(x==...
  • JAVA 判断是否为质数

    千次阅读 2020-02-16 23:12:56
    法一(for循环): 思路:对2——num/2的数遍历,如果num除以2——num/2之间的数有余数的话,就说明num为质数。 下面通过代码实现: import java.util.Scanner;... // 输入一个数并判断是否为质数 System.out.p...
  • Java寻找素数的高效算法

    千次阅读 2018-05-01 17:34:33
    在看Java语言程序设计进阶篇这本书,看一下找素数算法。具体要求是给出一个数n,打印出小于等于n的所有素数第一种方法,代码如下 : Scanner input = new Scanner(System.in); System.out.print("Find all ...
  • 判断素数最有效的算法

    万次阅读 多人点赞 2018-06-25 17:22:27
    目录 定义 1 常规方法判断 2 最有效方法判断 3 测试 ...约数只有1和本身的整数称为质数,或称素数。...1 常规方法判断 ... * 判断是否为素数/质数的常规方法 * 判断n是否为素数,根据定义直接判断从2到n-...
  • java 孪生素数几种算法

    千次阅读 2019-10-24 22:20:24
    1. 普通方法 public static boolean isPrime1(int x) { for (int i = 2; i <= x / 2; i++) { if (x % i == 0) { // 能被整除则不为素数 return false; } } ...
  • 素数最优算法

    2013-08-04 11:35:35
    最简单的算法素数~ 免去了繁杂的运算,节约时间
  • java判断素数的六种方法

    千次阅读 2017-05-22 16:56:51
    转载地址:...如果一个正整数只有两个因子, 1和p,则称p为素数. public boolean isPrime(int n) { if(n for(int i = 2; i if(n%i == 0) re
  • Java判断是否为素数

    2021-08-07 17:22:05
    质数(又称素数),是指在大于1的自然数中,除了1和它本身外,不能被其他自然数整除(除0以外)的数称之为素数(质数)。 //判断是否为素数,1不是素数。 public static boolean judge(int x){ for(int i=2;i<x;i++){//...
  • Java质数查找算法

    2020-11-06 22:37:10
    质数查找算法 1、其实将下面代码中的质数输出语句删除,还能再减少代码运行时间...
  • Java判断素数解析

    2020-05-06 22:18:32
    判断101~200之间有多少个素数,并输出所有素数。 程序分析:判断素数的方法:用一个数分别去除2到sqrt(这个数),如果能被整除,则表明此数不是素数,反之是素数。 注意:sqrt是指平方,在这的作用是提高运算速度,也...
  • Java 判断质数

    2020-03-23 17:51:12
    判断质数 什么是质数 质数是指在大于1的自然数中,除了1和它本身以外不再有其他因数的自然数。 所以1不是质数 代码示例 public static boolean isPrime (int x) { if (x==1) { //1不是质数 return false; ...
  • * 质数又称素数。一个大于1的自然数,除了1和它自身外,不能被其他自然数整除的数叫做质数;否则称为合数 * 100以内质数表 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 质数具有...
  • JAVA判断是否是素数的代码

    千次阅读 2018-04-15 23:02:22
    import java.util.*; class Prime{//注意无括号() private int m=0; public Prime(int m) { ... //判断是否是素数:除了1和它本身外,不能被其他自然数整除(除0以外)的数为素数,否则为合数 public S...
  • java质数判断/java素数判断

    万次阅读 2012-12-14 10:08:52
     如果一个正整数只有两个因子, 1和p,则称p为素数.  public boolean isPrime(int n)  {  if(n  for(int i = 2; i  if(n%i == 0) return false;  return true;  }  时间复杂度O(n).  2. 改进, ...
  • java 素数判断

    2020-10-31 18:30:14
    java 实现素数判断 代码 这个功能是判断一段范围内的素数,并打印到屏幕上。 public static void main(String[] args) { Scanner sc = new Scanner(System.in);//输入 System.out.println("请输入数的范围:"); ...
  • 题目:判断101-200之间有多少个素数,并输出所有素数。 疑问抛出:什么是素数? 答:除了1以外不能被自身或者其他数整出的数. 判断素数的方法:用一个数n分别去除去范围在2到sqrt这个数[2,sqrt(n)],如果能被整除,...
  • 判断是否为素数算法

    2021-05-20 17:40:42
    素数素数又称为质数质数是指在大于1的自然数中,除了1和它本身以外不再有其他因数的自然数。详情解释链接最小的素数是2int isprime(int n) { if(n<2){ return 0; } for(int j=2;j<=sqrt(n);j++){ if...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 10,582
精华内容 4,232
关键字:

java判断质数的算法

java 订阅