精华内容
下载资源
问答
  • Java筛选法求素数

    千次阅读 2017-09-13 10:06:24
    题目描述 给定一个正整数,编写程序计算有多少对质数的和等于输入的这个正整数,并输出结果。输入值小于1000。如,输入为10, 程序应该输出结果为2。...输出 2import java.util.Scanner; public class Ma

    题目描述
    给定一个正整数,编写程序计算有多少对质数的和等于输入的这个正整数,并输出结果。输入值小于1000。如,输入为10, 程序应该输出结果为2。(共有两对质数的和为10,分别为(5,5),(3,7))
    输入描述:输入包括一个整数n,(3 ≤ n < 1000)

    输出描述:输出对数

    示例1
    输入 10
    输出 2

    import java.util.Scanner;
    public class Main {
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            int x = sc.nextInt();
            int[] array = new int[x];   // 假设初始所有数都是素数,且某个数是素数,则其值为0;比如第一个数为素数那么array[0]为0
            array[0] = 1;   // 0不是素数
            array[1] = 1;   // 1不是素数
            // 下面是筛选核心过程
            for(int i = 2; i < Math.sqrt(x);i++) {   // 从最小素数2开始
                if(array[i] == 0) {
                    for(int j = i*i; j < x; j += i) {
                        array[j] = 1;   // 标识该位置为非素数
                    }
                }
            }
            //array为0的都是素数
            int res=0;
            for(int i=2;i<=x/2;++i){
                if( (array[i]==0)&&(array[x-i]==0)){
                    ++res;
                }
            }
            System.out.println(res);
        }
    }
    展开全文
  • java筛选法求素数

    千次阅读 2013-06-17 13:11:57
    import java.util.ArrayList; import java.util.Scanner; public class SieveMethod { int limits; ArrayList number = new ArrayList(); SieveMethod() { limits = 0; } private void
    package hu.sieve;
    
    import java.util.ArrayList;
    import java.util.Scanner;
    
    public class SieveMethod {
    	int limits;
    	ArrayList number = new ArrayList();
    
    	SieveMethod() {
    		limits = 0;
    	}
    
    	private void setLimits(int lim) {
    		limits = lim;
    		for (int i = 2; i <= lim; i++) {
    			number.add(i);
    		}
    	}
    
    	private void getPrime() {// 筛选出素数
    		for (int i = 0; i < number.size(); i++) {
    			for (int j = i + 1; j < number.size(); j++) {
    				if (number.get(j) % number.get(i) == 0) {
    					number.remove(j);
    					j--;
    				}
    			}
    		}
    	}
    
    	private void printPrime() {// 打印出素数
    		for (int i = 0; i < number.size(); i++) {
    			System.out.print(number.get(i) + " ");
    		}
    	}
    
    	public static void main(String[] args) {
    		SieveMethod prime = new SieveMethod();
    		Scanner scanner = new Scanner(System.in);
    		int num = scanner.nextInt();
    		prime.setLimits(num);
    		prime.getPrime();
    		prime.printPrime();
    	}
    }
    


    
    
    
    
    
    
    展开全文
  • public class PrimeNumber {//筛选法求N以内的质数(用数组完成的不太理想,当N很大时开销大) /** * @param args */ public static void main(String[] args) { int i,n=10; int...

    package cn.com.basicskill;

    public class PrimeNumber {//筛选法求N以内的质数(用数组完成的不太理想,当N很大时开销大)

    /**
    * @param args
    */
    public static void main(String[] args) {
    int i,n=10;
    int s=1;
    int a[] = new int [n];



    for(int k=0;k<n;k++){ //给数组A赋值
    a[k]=k;
    // System.out.println(k+"-"+a[k]+"-");
    }


    for(i=2;i<n;i++){ //
    for(int j=i+1;j<n;j++){
    if(a[j]!=0&&a[j]%i==0)
    {
    // System.out.println("the jjj is "+a[j]);
    a[j]=0;
    // System.out.println("the jjj is "+a[j]);
    // System.out.println("the i is "+i);
    // System.out.print("@"+j+"---"+"\n");
    }
    else
    {
    // System.out.print("the a[j] is "+a[j]);
    // if(a[j]>b[s-1]){ //这里之所以错,是因为凡是不被2整除的都放进来了
    // b[s]=a[j];
    // System.out.print("the s is "+s+"-"+b[s]+"\n");
    // s++;
    // continue;
    }
    }
    }
    int t=0;
    for(int k=0;k<n;k++){
    if(a[k]!=0){
    t++;
    System.out.println("-"+k+"-"+a[k]+"-");
    }
    }
    System.out.println("-the total number of primer number is "+t+"-");
    }


    }



    运行结果(当N=10时)
    -1-1-
    -2-2-
    -3-3-
    -5-5-
    -7-7-
    -the total number of primer number is 5-
    展开全文
  • 埃拉托色尼筛选法埃拉托色尼筛选法概念步骤优化代码 埃拉托色尼筛选法 概念 埃拉托色尼筛选法(the Sieve of Eratosthenes)简称埃氏筛法,是古希腊数学家埃拉托色尼提出的一种筛选法 作用: 产生一个不大于给定整数n...

    埃拉托色尼筛选法

    概念

    埃拉托色尼筛选法(the Sieve of Eratosthenes)简称埃氏筛法,是古希腊数学家埃拉托色尼提出的一种筛选法
    作用:
    产生一个不大于给定整数n的连续质数序列
    (质数是大于 1 并且只有 1 和 这个素数本身作为因数(因子) 的正整数。)

    步骤

    1. 初始化一个2~n的连续整数序列,作为候选质数(1只有它自己本身这一个因数。所以1既不是质数,又不是合数)
    2. 找到当前最小的数2,消去2的倍数,例如4,6,8等
    3. 再指向下一个最小的数3,消去3的倍数,例如6,9,12等
    4. 再指向下一个最小的数5,消去5的倍数,例如10,15,20等
      .
      .
      .
    5. 该算法 以这个方式不断的做下去直到序列中已经没有可以消去的元素为止,剩下的就是我们要求的质数

    优化

    • 根据上面的步骤我们发现有很多数字被重复消去,比如6被消去了两次
    • 消去x的倍数时,x2x^2不会大于n,p也不会大于n\sqrt[]{n}的向下取整的值(\lfloor n\sqrt[]{n}\rfloor,向下取整函数)以x2x^2 \le n作为判断循环的条件

    代码

    public int[] Sieve(int n) {
            int[] A = new int[n+1];
            for (int i = 2; i <= n; i++) {
                A[i] = i;
            }
            for (int i = 2; i <= Math.floor(n); i++) {
                if (A[i] != 0) {//没有被前面消除
                    int j = i * i;
                    while (j <= n) {
                        A[j] = 0;//标记已经删除
                        j = j + i;
                    }
                }
            }
            int s=0;
            int[] L = new int[n+1];
            for (int i = 2; i <= n; i++) {
                if (A[i] != 0) {
                    L[s] = A[i];
                    s = s + 1;
                }
            }
            return L;
        }
    
    展开全文
  • Java 素数筛选法

    2017-03-12 09:54:18
    素数筛选法
  • Java实现埃拉托色尼筛选法

    万次阅读 多人点赞 2019-07-20 21:43:16
    翻译:使用埃拉托色尼筛选法计算两个整数的最大公约数。(PS:最大公约数也称最大公因数,指两个或多个整数共有约数中最大的一个) 2 解决方案 2.1 埃拉托色尼筛选法原理简介 引用自百度百科: 埃拉托色尼筛选法(the...
  • 主要介绍了java使用筛选法求n以内的素数示例(java求素数),需要的朋友可以参考下
  • java素数筛选法

    千次阅读 2018-09-13 17:30:04
    素数筛选法: 从小到大遍历每一个数字,将其倍数筛去,剩下的即为素数。 class Test{ private boolean[] p; //用于标记对应下标的数字是否为素数 private int [] prime; private int len= 0 ; ...
  • 素数筛选法java

    2020-10-29 09:31:18
    import java.util.Scanner; public class 素数筛 { public static void main(String[] args) { // TODO Auto-generated method stub Scanner read = new Scanner(System.in); int n = read.nextInt(); ...
  • package javaapplication3;import java.util.*;... * 埃拉托色尼筛选法(the Sieve of Eratosthenes)简称埃氏筛法 * 未优化 */ public class JavaApplication3 { public static void main(String[] args) {
  • 素数筛选法java实现

    2013-09-22 17:33:48
    import java.util.Scanner; /** ... * 1~N内的素数筛选法  * 1、奇数赋值为true  * 2、奇数中从3开始到根号N,是其倍数的都置为false  * 3、输出奇数中任然为true的数组下标,下标即为素数
  • 筛选法求素数 java

    千次阅读 2016-09-13 10:44:34
    * 筛选法求素数 */ public class MainSogou2 { /* * from ~ to 是范围 */ public static boolean[] printPrime(int from, int to) { /* * 定义一个boolean类型的数组,长度为to+1; */ boolean[] ...
  • Java之实现:筛选法求素数

    千次阅读 2015-09-26 11:20:02
    不了解筛选法,还请自行百度,筛选法可以快速求的素数,不多说,直接上代码伺候! /** * 功能:筛选法求素数(主要是素数倍数的数,肯定不是素数) * @author Smilexs * @param severalPrime 第几个素数 */...
  • 筛选法求质数(Java实现)

    千次阅读 2018-07-22 20:51:13
    筛选法求质数:输入一个整数 n,求小于这个整数的所有质数。 算法:定义一个长度为 n 的 boolean 数组,true 表示是质数,false 表示不是质数。初始均为 true。 之后从 2 开始循环: import java.util.Scanner; /*...
  • 筛选法求素数 package itheima2; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int ...
  • 分析:素数(质数) : 只能够被1和这个数本身整除的数 1:用一个数分别去除2到这个数的平方(sqrt),如果能够被整除,则表明这个数不是素数,反之则为素数。为什么只除到sqrt呢?假如一个m 如果它不是素数,那它...

空空如也

空空如也

1 2 3 4 5 ... 13
收藏数 250
精华内容 100
关键字:

java筛选法

java 订阅