精华内容
下载资源
问答
  • Java求n以内的所有质数

    千次阅读 2015-11-03 21:59:26
    质数(prime number)又称素数,有无限个。一个大于1的自然数,除了1和它本身外,...方法3:基于规律“除了2,所有的质数都是奇数;如果一个数不能被它之前的质数整除,那么这个数是质数”进一步优化程序。 示例程序如

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

    方法1:根据质数的定义求解;

    方法2:对方法1作进一步优化,仅需判断到该数的平方根;

    方法3:基于规律除了2,所有的质数都是奇数;如果一个数不能被它之前的质数整除,那么这个数是质数”进一步优化程序。

    示例程序如下:

    package test;
    
    import java.util.ArrayList;
    import java.util.List;
    
    public class FindPrime {
    
    	public static void main(String[] args) {
    		long time = System.nanoTime();
    		System.out.println(findPrime1(10000).size());
    		System.out.println(System.nanoTime() - time);
    		
    		time = System.nanoTime();
    		System.out.println(findPrime2(10000).size());
    		System.out.println(System.nanoTime() - time);
    		
    		time = System.nanoTime();
    		System.out.println(findPrime3(10000).size());
    		System.out.println(System.nanoTime() - time);
    	}
    
    	public static List<Integer> findPrime1(int n) {
    		List<Integer> primes = new ArrayList<Integer>();
    		primes.add(2);
    		for(int i = 3; i <= n; i++) {
    			for(int j = 2; j < i; j++) {
    				if(i % j == 0)	break;
    				if(j == i-1)	primes.add(i);
    			}
    		}
    		return primes;
    	}
    
    	public static List<Integer> findPrime2(int n) {
    		List<Integer> primes = new ArrayList<Integer>();
    		primes.add(2);
    		for(int i = 3; i <= n; i++) {
    			int tmp = (int)Math.sqrt(i) + 1;
    			for(int j = 2; j <= tmp; j++) {
    				if(i % j == 0)	break;
    				if(j == tmp)	primes.add(i);
    			}
    		}
    		return primes;
    	}
    
    	public static List<Integer> findPrime3(int n) {
    		List<Integer> primes = new ArrayList<Integer>();
    		primes.add(2);
    		for(int i = 3; i <= n; i+=2) {
    			for(int j = 0; j < primes.size(); j++) {
    				if(i % primes.get(j) == 0)	break;
    				if(j == primes.size() - 1) { primes.add(i); break; }
    			}
    		}
    		return primes;
    	}
    
    }
    运行结果截图:


    结果分析:

    大家针对这个结果或许感到有点奇怪,为什么方法三会比方法二慢?虽然方法三理论上快点,但是方法三需要遍历list,而方法二不需要。除非当这个n特别大(我测到10^9,还是方法二优)时,不然方法二都是优于方法三的。所以我们认为最好的方法是:方法二 + 优化“除了2,所有的质数都是奇数”。

    展开全文
  • 100以内质数的算法

    2019-09-24 15:52:50
    质数:除了2,所有的质数都是奇数 质因子:质因子一定是质数 之前看到了个博客写的非常好,无可挑剔,所以就直接借用一下https://www.cnblogs.com/lzrabbit/articles/3706211.html 转载于:...
    质数:除了2,所有的质数都是奇数
    质因子:质因子一定是质数

    之前看到了个博客写的非常好,无可挑剔,所以就直接借用一下https://www.cnblogs.com/lzrabbit/articles/3706211.html

    转载于:https://www.cnblogs.com/xiaonangua/p/9176525.html

    展开全文
  • 输出小于N的所有质数(素数)

    千次阅读 2013-11-01 10:47:17
    1.除了2以外所有质数都是奇数,所以搜索N时,从3开始每次i+=2,可以少比较一半 2.偶数乘积一定是偶数,所以在搜索因数时,从3开始,每次i+=2又可以减少一半比较次数 3.在求x是否为质数时,i*i>x时即可退出循环,...

    输入N

    输出小于N的所有质数

    思路要点:

    1.除了2以外所有质数都是奇数,所以搜索N时,从3开始每次i+=2,可以少比较一半

    2.偶数的乘积一定是偶数,所以在搜索因数时,从3开始,每次i+=2又可以减少一半比较次数

    3.在求x是否为质数时,i*i>x时即可退出循环,再次减少比较次数

    #include<stdio.h>
    bool prime(int x)
    {
    int i;
    for(i=3;i*i<x;i+=2)
      if(x%i==0)
        return FALSE;
    return TRUE;
    }
    void main()
    {
    int n,i,j;
    printf("n=");
    scanf("%d",&n);
    printf("小于等于%d的质数\n",n);
    if(n>2)
    {
      printf("%4d",2);
      j++;
    }
    for(i=3;i<=n;i+=2)
      if(prime(i))
      {
        printf("%4d",i);//打印4位便于对齐
        if(j!=0 && ++j%10==0)//每行输出10个
        printf("\n");
      }
    printf("\n");
    }
    展开全文
  • JS 求质数

    千次阅读 2019-04-23 20:12:02
    2是最小的质数也是唯一的一个既是偶数又是质数的数,也就是说除了2以外,质数都是奇数。 方法一: for (var i = 2; i <= 10; i++) {//4 //假设所有的数都是质数 var flag = true; //通过嵌套循环找到 i ...

    质数:又称素数。一个大于1的自然数,除了1和它自身外,不能被其他自然数整除的数叫做质数。2是最小的质数也是唯一的一个既是偶数又是质数的数,也就是说除了2以外,质数都是奇数。

    方法一:

    for (var i = 2; i <= 10; i++) {//4
         //假设所有的数都是质数
       var flag = true;
         //通过嵌套循环找到 i 除了1 和本身以外所有可能出现的因子
       for (var j = 2; j < i; j++) {
         //判断 i 是否为质数
         if (i % j == 0) {//能进到当前的分支 说明不是质数
           flag = false;
         }
       }
         if (flag == true) {
         console.log(i);
       }
    }

    方法二:

     for (var i = 2; i <= 200; i++) {//4
         //假设所有的数都是质数
        var flag = true;
         //通过嵌套循环找到 i 除了1 和本身以外所有可能出现的因子
        for (var j = 2; j <= i / 2; j++) {
         //判断 i 是否为质数
             if (i % j == 0) {//能进到当前的分支 说明不是质数
                flag = false;
                break;
             }
         }
            if (flag) {
         // if (flag == true) {
         console.log(i);
         }
      }

    方法三:

    
        l: for (var i = 2; i <= 20; i++) {//4
            //通过嵌套循环找到 i 除了1 和本身以外所有可能出现的因子
            for (var j = 2; j <= Math.sqrt(i); j++) {//16  8
                //判断 i 是否为质数
                if (i % j == 0) {//能进到当前的分支 说明不是质数
                    continue l;
                }
            }
            console.log(i);
        }

    PS:①求开平方

     console.log(Math.sqrt(64));//8

             ②求一个数的n次方

    console.log(Math.pow(2,3));//8

     

    展开全文
  • 用java求一定范围内的质数

    千次阅读 2008-11-06 10:17:00
    用java求一定范围内的质数 除了2要特殊处理以外,所有质数都是奇数,给定一个奇数i,判断从3开始到它自身的开方之间的所有奇数是否能整除就行了,这是最快的方法。 for (int i = min; i int temp = (int) Math.sqrt...
  • 质数相关

    2017-09-18 10:42:01
    (1)从2开始,2最小的质数。(2)除了2之外的偶数全都不是质数,因为除了1和自身之外它们还能被2整除。若为大于2的奇数,则进入下一步继续判断。(3)将其开方,若从3到开方向下取整之间的所有奇数都不能将其整除...
  • 除了2以外所有的质数都是奇数 ②.任何正整数N只能有一个大于根号N的质因子 ③.任何小于正整数N的合数都有小于根号N的因子 Eratosthenes筛选法是用来寻找质数的算法,原理是这样的:比如求小于...
  • 求一亿以内回文质数(素数)

    万次阅读 多人点赞 2020-02-29 23:08:56
    所以,偶数位回文数除了11都是合数。 观察偶数位回文数,提取所有奇数数字,与提取所有偶数位数字,正好是相反顺序。 因此,偶数位数和等于奇数位数和,从而差等于0,而0能被11整除,因此这个回文数,...
  • 什么叫做质数

    2010-09-20 00:20:18
    自然数:用以计量事物件数或表示事物次序数 。 即用数码0,1,2,3,4,……所表示数 。自然数由0开始 , 一个...除了2以外,所有质数都是奇数。 质因数; 每个合数都可以写成几个质数相乘形式,这几个质数都...
  • 由于四是大于二唯一偶数,需要偶数素数2才能写成两个素数之和,因此,哥德巴赫猜想另一种形式是,所有大于4偶数整数都是哥德巴赫数。 将给定偶数表示为两个质数的和称为该数Goldbach分区。 以下是一些偶数...
  • 质数问题

    2012-01-31 10:13:00
    求1~N之间的所有质数 1、试除法: ...3)除了2以外,x所有可能质因数都是奇数,所以先尝试2,然后从3~x/2的所有奇数 4)由于因数是成对出现。比如,100因数有:1和100,2和50,4和25,5和2
  • 筛子法求质数

    千次阅读 2013-12-27 18:31:38
    给你一个自然数N,求[6,N]之内的所有素数中,两两之和为偶数的那些偶数。...//因为质数除开2以外都是奇数,那么大于6的偶数都是奇数,那么把6~N之间的质数都求出来,打印两两的和就可以了。 int main(){ cout
  • 除了2之外,所有的质数都是奇数,因此一个奇数只有减2后才可能是质数,因为奇数-偶数=奇数,但如果减4那就必然不可能是两个质数之和了 比如27不能由2+素数构成所以结果是3 #include<iostream> using n...
  • 一开始以为是100万的所有数字,题目要求是只要偶数,也可以分析出来,如果是给一个奇数,当我们给他大于等于3奇数(这个数加有可能不是质数,但至少满足是奇数,至于是不是质数还要自己判断),剪出来一定是个偶数...
  • C语言练习02:搜索质数之一

    千次阅读 多人点赞 2011-10-18 15:18:05
    这个练习中,我们将基于《C语言练习01:单向链表的实现》中实现的链表程序实现一个搜索某一范围内所有质数的程序。...2是唯一的偶数质数,2以后所以后的质数都是奇数。所以我们程序中搜索质数的时候没有从2开始
  • 算法第1步就是写下从3至某个上限之间的所有奇数。在算法剩余部分,遍历整个列表并剔除所有不是质数的奇数。在3之后把每逢第3个数(3倍数)...原因在于,我们待筛选列表中的所有数字都是奇数。一开始就直接从...
  • 这意味着所有的质数都是奇数 相邻两个一个是奇数,一个是偶数 所以整张图是一个二分图然后跑网络流 源点对奇数点连容量为 2的边 偶数点对汇点连容量为 2的边 中间奇数点对偶数点连容量为 1的边 表示每个点至多...
  • 统计所有小于非负整数 n 的质数的数量。 示例: 输入: 10 输出: 4 解释: 小于 10 的质数一共有 4 个, 它们 2, 3, 5, 7 。 思路如果一个数质数,那么它的倍数一定不是质数和偶数不是质数两个特点解题。创建...
  • 题目描述: 功能:输入一个正整数,按照从小到大的顺序输出它的所有质数的因子(如180的质数因子为2 2 3 3 5 ),最后一个数后面也要有空格。 输入描述: 输入一个long型整数 ...- 质数除2以外都是奇数; -
  • 遍历模除质数筛选法

    2018-06-04 17:08:42
    算法逻辑解析:一个数a除以a前边所有的质数都除不尽,则a也为质数。 此例中,Prime[]数组存放已确认的质数,偶数跳过,直接确认奇数是否为质数。 易错点:核心逻辑a于Prime[]数组中已存在的数都要判断,都除不尽a...
  • P1217 [USACO1.5]回文质数 Prime Palindromes 题解 1.理解题意: 回文质数,它既是回文数,又是质数 我们可以先找出范围内所有回文...(2)所有偶数位回文数除了11不是质数,所以回文质数一定是奇数位 ...
  • 计数小于输入n的质数 题目描述 统计所有小于非负整数 n 的质数的数量,n输入。 示例: 输入: 10 输出: 4 解释: 小于 10 的质数一共有 4 个, 它们 2, 3, 5, 7...以6为步长,首先所有的大于5的整数可以用公式 6x+...
  • 质数,素数,合数

    千次阅读 2009-04-22 11:12:00
    其他则成为合数质数和素数指是同一个概念1即不是质数,又不是素数质数中除2是偶数外,其他都是奇数著名高斯说过:任何一个整数,都可以写成一串质数相乘积。「唯一分解定理」原帖地址: http
  • 统计所有小于非负整数 n 的质数的数量。 示例 输入: 10 输出: 4 解释: 小于 10 的质数一共有 4 个, 它们 2, 3, 5, 7 。 关于质数的筛选,江湖中传说着一个方法 ————埃拉托斯特尼筛法 大致步骤: 我们知道 2 ...
  • 群友提出过程和现在网上随意查到的都差不多,无非遍历奇数,然后判断奇数小于奇数一定值的所有数中,没有可以整除数。但是我想到这样遍历,当判断一个数是否为要判断数因子时,这个数可能又有小...
  • 方法三思路:将数组中所有的2的倍数标记为false(不是质数),数组中剩下的最小的数字就是3,他不能被更小的数整除,所以3素数,再将数组中所有的3的倍数标记为false……以此类推,其实就是将每个奇数的倍数去掉,...
  • 考虑到质数只有可能是奇数+偶数构成的(222 除外,不过 222 只能由 1+11+11+1 凑成,所以我们考虑时只考虑一个 111,其余的 111 全部不选),所以不妨将所有的数按奇偶分类,构成一个二分图。 然后如果两个数加起来...
  • 质素 质数又称素数。一个大于1自然数,除了1和它自身外,不能被其他自然数整除数叫做质数;否则称为合数。...所有大于5的奇数中,个位为5的都是合数。 根据定义判断一个数是不是质素 x = int(input('>...
  • 本算法直接跳过了所有的偶数和个位为5的奇数,即只测试个位为1、3、7、9的整数n是不是质数。测试n是否为质数时,不是测试3~sqrt(n)之间的全部整数,而是测试3~sqrt(n)之间的全部质数,勉强算是比较高效的算法。

空空如也

空空如也

1 2 3 4 5 ... 8
收藏数 141
精华内容 56
关键字:

所有的质数都是奇数