精华内容
下载资源
问答
  • 找出质数

    2018-12-06 09:46:42
    package javademo1; public class Zhishu { public static void main(String[] args) { // TODO Auto-generated method stub int n=201;...//x的值为1,表示是质数,0就不是质数 wh...
    package javademo1;
    
    public class Zhishu {
    
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    		int n=201;
    		while(true){
    		int i=2;
    		int x=1;//x的值为1,表示是质数,0就不是质数
    
    		
    		while(i<n){
    			if(n%i==0){
    				x=0;
    				break;
    			}
    			i++;
    		}
    		if(x==1){
    			System.out.println("200以上的最小质数为:"+n);
    			break;
    		}
    		n++;
    		}
    		
    	}
    
    }
    
    
    展开全文
  • 74 找出质数

    2020-03-27 09:55:57
    74 找出质数 作者: SunCiHai时间限制: 10S章节: 字符串 问题描述 : 明明学习数学已经有一段时间了。一次老师在课上讲了什么叫质数质数就是大于等于2且只能被1和其本身整除的整数。明明觉得这很简单,以为这很容易...

    74 找出质数

    作者: SunCiHai时间限制: 10S章节: 字符串

    问题描述 :

    明明学习数学已经有一段时间了。一次老师在课上讲了什么叫质数。质数就是大于等于2且只能被1和其本身整除的整数。明明觉得这很简单,以为这很容易掌握,于是就不多做练习。明的爸爸发现了这个问题,他想让明明多做练习,把质数这个知识点掌握牢固。但是,他也知道只是求质数会很无聊,明明一定不愿意多做。于是他想出了一个游戏,这个游戏叫“找出质数”,就是给明明一个数字串,要叫明明在这个数字串中找出一个最大的子串,要求这个子串是一个质数。 但是由于明明还太小,他的计算能力有限,因此明明的爸爸认为,找出长度大于4个字符的质数对明明来说太困难了。于是他降低了要求,只需找出小于10,000的最长的质数子串即可。 例如:有一个数字串为17,最大的子串就应该是17,因为1不是质数,7虽然是质数,但是7的长度只有1,17也是质数,它的长度为2,因此最大的子串就是17。 明明觉得这个游戏很有趣,就高兴地做了起来,明明的爸爸出了很多个数字串,由于数字串太多,所以明明爸爸自己找出最长的子串也要花很多的时间,于是明明的爸爸想让你帮他一个忙,写一个程序,找出数字串中最长的质数子串。

    明明爸爸的问题可以归结为:输入一串数字,找出其中最长的不超过4个字符的质数子串。若有多个答案,则找出其中数值最大的一个。

    输入说明 :

    你写的程序要求从标准输入设备中读入测试数据作为你所写程序的输入数据。标准输入设备中有多组测试数据,每组测试数据仅一行,每组测试数据为一个数字串,数字串的长度不超过20。每组测试数据与其后一组测试数据之间没有任何空行,第一组测试数据前面以及最后一组测试数据后面也都没有任何空行。

    输出说明 :

    对于每一组测试数据,你写的程序要求计算出一组相应的运算结果,并将这一组运算结果作为你所写程序的输出数据依次写入到标准输出设备中。每组运算结果为一个整数,即最长的不超过4个字符的质数子串(测试数据保证这个子串存在);若有多个答案,则输出其中数值最大的一个。每组运算结果单独形成一行数据,其行首和行尾都没有任何空格,每组运算结果与其后一组运算结果之间没有任何空行,第一组运算结果前面以及最后一组运算结果后面也都没有任何空行。 注:通常,显示屏为标准输出设备。

    输入范例 :

    17
    121
    1113
    输出范例 :

    17
    2
    113

    #include<stdio.h>
    #include<stdlib.h>
    #include<math.h>
    #include<string.h>
    int isPrimeNumber(int n);
    int main(){
    	char str[21];
    	int i,j,k,max,t,len;
    	while(scanf("%s",str)!=EOF){
    		len=strlen(str);
    		max=0;
    		for(i=4;i>0;i--){
    			for(j=0;j<=len-i;j++){
    				t=0;
    				for(k=0;k<i;k++){
    					t=t*10+(str[j+k]-'0');
    				}
    				if(isPrimeNumber(t)&&t>max){
    					max=t;
    				}
    			}
    		}
    		printf("%d\n",max);
    	}
    	return 0;
    }
    
    int isPrimeNumber(int n){
    	if(n==1){
    		return 0;
    	}
    	for(int i=2;i<=sqrt(n);i++){
    		if(n%i==0){
    			return 0;
    		}
    	}
    	return 1;
    }
    
    展开全文
  • 如何快速查找质数

    千次阅读 2019-11-21 23:06:21
    那么,如何能简单快速地找出质数呢? 埃拉托斯特尼筛法 埃拉托斯特尼(Eratosthenes)是一位古希腊数学家、地理学家、历史学家、诗人、天文学家,也是阿基米德的好基友。除了发明质数的筛选方法,他还测量地球周长...

    质数(素数),指在大于 1 的自然数中,除了 1 和该数自身外,无法被其他自然数整除的数(如 2,3,5,7,11 ……)。那么,如何能简单快速地找出质数呢?

    埃拉托斯特尼筛法


    埃拉托斯特尼(Eratosthenes)是一位古希腊数学家、地理学家、历史学家、诗人、天文学家,也是阿基米德的好友。除了发明质数的筛选方法,他还测量地球周长、日地间距、地月间距,编排星图,绘制地图,把名字写在月球上(埃拉托斯特尼陨石坑)。

    牛人一牛就是几千年

    埃拉托斯特尼筛法(sieve of Eratosthenes )用来找出一定范围(n)内的所有质数。其方法是从 2 开始,在 n \sqrt{n} n 以内,将每个质数的倍数剔除掉,剩下的就是所求范围的质数。例如找 100 以内的质数,先把 2 的倍数筛掉(保留 2),再把 3 的倍数筛掉(保留 3),如此重复下去,直到 7 的倍数被筛掉(因为下一个质数 11 已经大于 100 \sqrt{100} 100 ),剩下的就是 100 以内的质数。

    在这里插入图片描述


    一个亿的小目标


    王先生说: “最好先定一个能达到的小目标,比方说我先挣它一个亿”。挣一个亿,我太难了,不如先 “算一个亿” 吧。下面我们就用埃拉托斯特尼筛法来找 1 亿以内的质数,为了方便,结果只输出该范围内质数的个数。

    Python

    • 方式一:列表

    先创建一个包含 N+1 个 True 的列表,然后把非质数设为 False,最后剩下的 True 就是质数。

    N = 100000000
    primes = [ True for i in range(N) ]
    primes[:1] = [ False, False ]  # 去掉0和1
    
    k = 2 
    while k * k <= N:
        if primes[k]:
            j = k * k
            while j <= N:
                primes[j] = False
                j += k
        k += 1
    
    print("{} primes in {}".format(primes.count(True), N))
    

    结果:

    5761455 primes in 100000000
    

    耗时 67 秒

    • 方式二:集合

    我们还可以用集合的方式来筛选,先创建一个从 3 到 N 的奇数集合(加上 2),然后减去每个质数的倍数的集合,最后得到只有质数的集合(代码缩减了一半)。

    N = 100000000
    primes = {i for i in range(3, N + 1, 2)} | {2}
    
    for j in range(3, int(N ** 0.5) + 1, 2):
        if j in primes:
            primes -= {i for i in range(j * j, N + 1, j)}
    
    print("{} primes in {}:".format(len(primes), N))
    

    耗时 59 秒,有进步。( 仿佛听到有人喊: “偷步啊!你从奇数开始筛。“ 答:“是,又怎样😆!” )

    • 方式三:函数

    看到 Wiki埃拉托斯特尼筛法 的 python 代码,写得真简练,拿来试试。

    def eratosthenes(n):
         IsPrime = [True] * (n + 1)
         for i in range(2, int(n ** 0.5) + 1): 
             if IsPrime[i]:
                 for j in range(i * i, n + 1, i): 
                     IsPrime[j] = False
         return {x for x in range(2, n + 1) if IsPrime[x]}
    
    N = 100000000
    primes = eratosthenes(N)
    print("{} primes in {}:".format(len(primes), N)) 
    

    耗时一下子降到 26 秒,凭什么啊,如果把函数拆了,会增加 10 秒,暂时没搞懂。

    Go

    现在算法已经不是问题,时间才是问题,我要尽快算到一个亿。于是我写了一段憋足的 Go 代码。

    package main
    import "fmt"
    
    func main() {
        N := 100000000
        primes := make([]bool, N+1)
        for i := 2; i <= N; i += 1 { 
            primes[i] = true
        }   
    
        for k := 2; k*k <= N; k += 1 { 
            if primes[k] {
               for j := k*k; j <= N; j += k { 
                   primes[j] = false
               }   
           }   
       }   
    
       total := 0
       for i := 0; i <= N; i++ {
           if primes[i]{
               total += 1
           }   
       }   
       fmt.Println(total, "primes in", N)
    
    }
    

    go run 一下,1 个亿耗时仅 1.5 秒!这速度堪比双十一的第 1 秒。

    在一个亿面前,Python 被 Go 打得满地找牙,解释型就是打不过编译型吗?

    这时,Python 背后传来一个坚实的声音:“别怕,有我在!”

    Python + C++

    这个背后的声音是 primesieve-python,一个调用 primesieve C++ library 的 Python 模块。

    安装: pip3 install primesieve

    少啰嗦,给我上!

    import primesieve
    N = 100000000
    prime = primesieve.primes(N)
    print(len(prime), "primes in", N)
    

    1 个亿耗时 0.5 秒 !10 个亿 4.5 秒

    如果只需要质数的个数,直接调用 primesieve.count_primes(N),1 亿只需 0.06 秒,1000 亿只需 30 秒。

    Python 成功逆袭,Go 表示请外援不算好汉~


    总结


    最后,我们统计一下以上各种求质数方式的效率(耗时):

    系统环境: MacOS 10.14.4 / 2.6 GHz Intel 2-Core i5 / 8GB DDR3 / SSD

    N以内质数的个数Python / 列表Python / 集合Python / 函数GoPython / primesieve
    10万95920.09s0.07s0.10s0.006s0.03s
    100万784980.6s0.3s0.25s0.01s0.04s
    1000万6645796.1s3.7s2.6s0.10s0.11s
    1亿57614551m7s54s26s1.6s0.54s
    10亿50847534算了吧压力太大太难了15s4.5s
    20亿9822228732s10s
    30亿14444953753s24s
    40亿1899618121m17s44s
    50亿2349542231m49s1m1s
    60亿2795453682m31s1m25s
    100亿455052511>100m以下用 count_primes(n)
    2s
    200亿882206716楼上…5s
    300亿13000059268s
    400亿171195543311s
    500亿211965457814s
    1000亿411805481330s

    (完)

    展开全文
  • 找出范围内所有质数

    2013-11-13 20:16:03
    这个程序需要你输入一个整数,该程序能找出从1到该整数内的所有质数并且输出。
  • 找出质数算法之二

    2017-03-19 11:27:57
    public class 第二版 { public static void main(String[] args) { int count = 0;//计数变量 int number = 2; int squareRoot = 1;//这个变量记录平方根 while(number ...if(number == (squareRoot+1

    public class 第二版 {

    public static void main(String[] args) {
    int count = 0;//计数变量
    int number = 2;
    int squareRoot = 1;//这个变量记录平方根
    while(number<10000){
    boolean isPrime = true;
    if(number == (squareRoot+1)*(squareRoot+1)) squareRoot++;

    for(int i =2;i<= squareRoot;i++){
    if(number % i == 0){
    isPrime = false;
    break;
    }
    }
    if(isPrime){
    count++;
    System.out.println(number);
    }

    number++;
    }

    System.out.println("一共有"+count+"个素数");
    }


    }
    展开全文
  • //找出max以内的所有质数 function prime(max) { max = Math.floor(max) // 判断是否小于一,如果是那么就没有质数 if (max < 1) { return [] }; // 定义一个数组来存放所有的质数 let primeArr = []; // ...
  • 进阶74 找出质数

    2020-04-24 00:11:27
    74 找出质数 作者: SunCiHai时间限制: 10S章节: 字符串 问题描述 : 明明学习数学已经有一段时间了。一次老师在课上讲了什么叫质数质数就是大于等于2且只能被1和其本身整除的整数。明明觉得这很简单,以为这很容易...
  • 进阶题74 找出质数

    2020-03-24 12:29:48
    74 找出质数 作者: SunCiHai时间限制: 10S章节: 字符串 问题描述 : 明明学习数学已经有一段时间了。一次老师在课上讲了什么叫质数质数就是大于等于2且只能被1和其本身整除的整数。明明觉得这很简单,以为这很容易...
  • 101 找出质数 问题描述 : 明明学习数学已经有一段时间了。一次老师在课上讲了什么叫质数质数就是大于等于2且只能被1和其本身整除的整数。明明觉得这很简单,以为这很容易掌握,于是就不多做练习。明的爸爸发现了这...
  • 找质数的三种方法

    千次阅读 2018-03-21 20:35:23
    package 归档; /** * @autor aachen0 * @create 2018/3/19 17:22 * IDE:IntelliJ IDEA * 求100到200内的所有质数 */ public class FindPrimer { public static void main(String[] args) { find(); ...
  • 算法---快速查找质数

    千次阅读 2018-07-21 13:16:18
    其实,一个质数,很简单啊,就是全部遍历一次嘛, 但是! 我们这里讲一下,快速求解的办法好吧! 对于给定的一个数,求解这个数内的所有质数! 首先,对于一个数n,只要它根号n内的数,不能整除它,那么它就...
  • python 中从list表中找出质数

    千次阅读 2018-09-22 23:43:05
    –很抱歉之前上传了一个错误的方法,后来自己检查发现是错的。以下是我花了半个小时写的,真的对不起之前的那些看了我的博文的同行。希望大家发现有错一定要留言告诉sept,这样我才能知错能改 def zhishu(List): ...
  • 质数 素数
  • 问题后,首先需要解决,什么是质数的问题。与纯数学的想法不同,我们需要找到一个可以让计算机接受的判定的法则。质数,就是除了1以及本身以外,没有其他因数的自然数。首先它是个自然数,因此程序的输入端就...
  • Java:找出100以内的质数(一)。

    万次阅读 多人点赞 2019-01-06 01:54:36
    Java:找出1~100之间的质数。  质数(prime number)又称素数,有无限个。质数定义为在大于1的自然数中,除了1和它本身以外不再有其他因数。  由以上的定义我们可以延伸出另一种解释:这个数与除1之外小于它的...
  • 筛选法(求1~n中的质数) 用来除以2的倍数,是合数就置为0. 用来除以3的倍数,是合数就置为0. 用来除以4的倍数,是合数就置为0. … 用来除以√n的倍数,是合数就置为0. void isPrime(int n){ int[] arrays=new int...
  • 如何找出1-100之间的质数

    千次阅读 2019-08-17 10:23:10
    打印1-100以内的质数 1.了解什么是质数? 只能被1和其本身整除的数就是质数,1不是质数。 2.利用for循环来定义1-100这个范围; for(var i=1;i<=100;i++) 3.定义一个变量来记录i可以整除(对比其小的所有自然数...
  • 找出质数算法之一

    2017-03-19 11:20:11
    public class 第一版 { public static void main(String[] args) { int count = 0;//计数变量 int number = 2; while(number boolean isPrime = true; for(int i =2;i if(number % i == 0){ ...
  • 面试题:找出1至1000以内的质数 打印1~1000以内所有质数 质数:只能被1和它本身整除的数。如: 10以内的质数: 2 3 5 7 任何的偶数(除2以外)都是非质数 但1不是质数 代码如下: public static void main(String...
  • 主要介绍了JavaScript实现找质数代码分享,本文直接给实现代码,需要的朋友可以参考下
  • 找出质数算法之四

    2017-03-19 11:35:53
    public class Eratosthenes算法 { public static void main(String[] args) { int n = 27; int[] primes= new int[n+1]; for (int k = 2; k if (primes[k]==0) { ...System.out.println
  • def is_prime(num): 案例2:计算输入的任意两个数之间所有的质数的和 分析:刚才已经定义了判断一个是否为质数,现在需要再定义一个可以计算两个数之间所有的质数的和的函数,并把计算结果返回给调用者。...
  • 代码如下: import math def isprime(num): for i in range(2,int(math.sqrt(num))+1): if num%i == 0: return False return True count = 0 for i ...1 print(f'\n1000以内质数的个数是:{count}') 结果如下:
  • python找质数

    2017-12-29 19:07:00
    python找质数对 ... 例如输入一个正整数10,可以找出有“3+7=10”、“5+5=10”两个质数对的和为10。 要实现这个功能的python脚本如下所示: def isprime(num): for i in range(2, num): ...
  • 1.有一组正整数数据,找出其中的质数及其个数,并求出数据中质数的和。要求用函数is_prime(x)实现质素判断,可考虑用函数prime_sum()实现质素求和处理,不做要求。(30分) 例如:假设正整数数据为:56,41,70,31,83...
  • 实现如下功能: 输入一个数字10 输出前10个质数:2 3 5 7 11 13 17 ...3. 从2开始判断是否为质数,如果是质数则存入到数组中,如果不是质数判断下 一个数是否为质数,当数组被填满后循环结束 代码如下: package come...
  • 本文主要介绍了c语言求给定范围内的所有质数的小程序。具有很好的参考价值。下面跟着小编一起来看下吧
  • 用Python寻找质数

    千次阅读 2019-10-27 20:48:43
    判断是否是质数的方法 import random def rabinMiller ( num ) : # Returns True if num is a prime number . s = num - 1 t = 0 while s % 2 == 0 : # keep halving s while...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 33,541
精华内容 13,416
关键字:

怎么找出质数