精华内容
下载资源
问答
  • 统计找出一千万以内,一共有多少质数 质数概念: 只能被1和自己整除的数 public class Test3 { public static void main(String[] args) { int sum=0; for (int i = 1; i <=10000000; i++) { if (isPrime...

    统计找出一千万以内,一共有多少质数

    质数概念: 只能被1和自己整除的数

    public class Test3 {
    	public static void main(String[] args) {
    		int sum=0;
    		for (int i = 1; i <=10000000; i++) {
    			if (isPrime(i)) {
    				sum++;
    			}	
    		}
    		System.out.println(sum);
    	}
    
    	private static boolean isPrime(int i) {
    		for (int j =2; j <=Math.sqrt(i); j++) {
    			if (0==i%j) {
    				return false;
    			}
    		}
    		return true;
    	}
    }
    
    展开全文
  • Problem Description Give you a lot of positive integers, just to find out how many prime numbers there are. Input There are a lot of cases. In each case, there is an integer N representing ...
  • def prime_number ( ) : import ... not_prime_number_group ...#通过不是素数的列表,产生是素数的列表 ...'101到200一共有 %d 个素数' % ( len ( prime_number_group ) ) ) prime_number ( )
    def prime_number() :
        import random
        not_prime_number_group = []
        prime_number_group = []
        for number in range(101 , 201 , 1) :
            number1 = int(number/2)
            for i in range(2 , number1 + 1) :
                if number % i == 0 :
                    not_prime_number_group.append(number)
                    break
                '''else:
                    prime_number_group.append(number)因为存在于循环里面,所以输出时会输出很多次'''
        #通过不是素数的列表,产生是素数的列表
        for number in range(101 , 201 , 1) :
            if number not in not_prime_number_group :
                prime_number_group.append(number)
        print(prime_number_group)
        print('101到200一共有 %d 个素数' % (len(prime_number_group)))
    prime_number()
    
    展开全文
  • 质数概念: 只能被1和自己整除的数 ** 初步思路 **:运用双层循环,判断是否为质数,true则num+1;false跳过 代码如下: package somethings; import java.util.Locale; /** * @author Small_Tsky * @date 2020/2...

    质数概念: 只能被1和自己整除的数

    **

    初步思路

    **:运用双层循环,判断是否为质数,true则num+1;false跳过

    代码如下:

    package somethings;
    
    import java.util.Locale;
    
    /**
     * @author  Small_Tsky
     * @date 2020/2/23 - 16:21
     **/
    public class Unimportance {
    
          public static void main(String[] args) {
    
                long start = System.currentTimeMillis();
                int n = 10000000 ;
    //        初始化num (因为2为质数未被计入for循环里)
                int num = 1;
    
                for (int i = 3; i <= n; i++) {
                    for (int j = 2; j <i ; j++) {
    //                i除1和本身没有其他的因子,即为质数
                        if (i % j != 0) {
                            num++;
                        }
                    }
                }
    
                System.out.println("一千万以内的质数个数为:"+num);
                long end = System.currentTimeMillis();
                System.out.println("所用时间:"+(end - start)+"毫秒");
            }
        }
    
    

    运行结果: 无

    数据过于庞大,运算次数要循环1+2+…+(10000000-2)次。
    这个算法的时间复杂度是:O( N 2 N^2 N2)
    每秒十亿指令的计算器运行时间复杂度为 n 2 n^2 n2,其中n= 1 0 6 10^6 106,所运行的时间为
    16.67min
    ,而运行一千万则需要的时间为1667min,即27.8h,所以要等到结果出来需要等上一天多。

    -------------------------------------------------------------------

    如果复杂度是 N 2 N^2 N2,要下意识将复杂度改为 N l o g N NlogN NlogN,所以下面需要做的就是优化优化思路

    优化思路:

    对于确定的质数先做标记,标记完成后,遍历标记的质数,num++;

    代码如下:

    import java.util.Arrays;
    
    /**
     * @author Small_Tsky
     * @date 2020/2/23 - 16:25
     **/
        public class Isprimes {
                public static void main(String[] args) {
                    long start = System.currentTimeMillis();
                    int n = 10000000 +1;//	下标从1开始
                    int num = 0;
                    boolean [] isprimes = new boolean[n];
    //                定义isprimes[]
                    Arrays.fill(isprimes,true);
                    for (int i = 2; i <= isprimes.length; i++) {
                        for (int j = 2; i * j < isprimes.length; j++) {
    //                        标记不符合条件的num,即有因子的全部标记false;
                            isprimes[i * j] = false;
                        }
                    }
         
                    isprimes[1]=false;//注意:1为非质数
                    
    //                  遍历isprimes[]
                    for (int i = 1; i <isprimes.length ; i++) {
                        if (isprimes[i]){
                            num++;
                        }
                    }
                     long end = System.currentTimeMillis();
            System.out.println("一千万以内的质数一共有 " + num + " 个");
            System.out.println("所用时间为 " + (int) (end - start)+"毫秒");
    }
    }
    

    运行结果:

    
    一千万以内的质数一共有 664579 个
    所用时间为 985毫秒
    
    Process finished with exit code 0
    

    此算法的时间复杂度是:O(NlogN)

    -----------------------------------------------------------------------

    前辈思路(埃氏筛法):

    埃拉托斯特尼筛法:简称埃氏筛或爱氏筛,是一种由希腊数学家埃拉托斯特尼所提出的一种简单检定素数的算法。要得到自然数n以内的全部素数,必须把不大于根号n的所有素数的倍数剔除,剩下的就是素数。

    思想实现:要得到自然数n以内的全部素数,必须把不大于的所有素数的倍数剔除,剩下的就是素数。
                  给出要筛数值的范围n,找出以内的素数。先用2去筛,即把2留下,把2的倍数剔除掉;再用下一个质数,也就是3筛,把3留下,把3的倍数剔除掉;接下去用下一个质数5筛,把5留下,把5的倍数剔除掉;不断重复下去…。

    代码如下:

    package arrylist;
    
    import property.Item;
    
    import java.util.Arrays;
    
    /**
     * @author Small_Tsky
     * @date 2020/2/23 - 16:30
     **/
    public class list  {
    
        public static void main(String[] args) {
            long start = System.currentTimeMillis();
    
            int n = 10000000 + 1;   //总数,下标从1开始
            boolean[] data = new boolean[n];        //存储是否为质数的容器
            Arrays.fill(data, true);    //  先假设都是质数
            for (int i = 1; i <= data.length; i++) {    //  遍历容器
                if (i % 2 == 0) {
                    data[i] = false;    //  先将为偶数排除
                }
            }
            data[2] = true;//  2为质数
            data[1] = false;//注意:1不是质数
    
            for (int i = 2; i <= Math.sqrt(n); i++) {   //优化:只需考虑根号n以内的数的倍数
                if (data[i]) {  //    这里的i为非偶数(上一步已经把偶数排除了),剩下只有非偶数
                    //  非偶数的平方为非质数,其平方的倍数也一定是非质数
                    for (int j = i * i; j < n; j += 2 * i) {   
                        data[j] = false;    //优化:如果一个数(i * i)不是质数,那么它的倍数(i*i+2*i)一定不是质数
                    }
                }
            }
    
            int num = 0;    //  计数质数总数
            for (int i = 1; i < data.length; i++) {
                if (data[i]) {
                    num++;  //  为质数则+1
                }
            }
            long end = System.currentTimeMillis();
            System.out.println("一千万以内的质数一共有 " + num + " 个");
            System.out.println("所用时间为 " + (int) (end - start) + "毫秒");
        }
    }
    

    运行结果:

    一千万以内的质数一共有 664579 个
    所用时间为 98毫秒
    

    此算法的时间复杂度是:O(N)

    #第三种结果比第二种结果足足快了800多毫秒#

    所以时间复杂度越小越好,但是如果算法效率过高的话,很有可能出现错误

    展开全文
  • 首先素数是指这个数只有1和它本身相乘,不能被2,3,5,7整除。所以我们可以根据这个特性。作出以下程序代码: #include <iostream> using namespace std; int main() { float a,b,c,d,e;//存放数,随便设置 ...

    首先素数是指这个数只有1和它本身相乘,不能被2,3,5,7整除。所以我们可以根据这个特性。作出以下程序代码:

    #include <iostream>
    using namespace std;
    int main()
    {  
      float a,b,c,d,e;//存放数,随便设置
          e=0;//素数的个数

        cout<<"2"<<endl;
        cout<<"3"<<endl;
        cout<<"5"<<endl;
        cout<<"7"<<endl;
      for(int i=7;i<=100;i++)//7之前有4个素数(2,3,5,7)所以要把这四个包含进去
       { a=i%2;
         b=i%3;
         c=i%5;
         d=i%7;
       if(a>0&&b>0&&c>0&&d>0)
           {
               cout<<i<<endl;
               e++;
           }
       }

    cout<<"素数一共:";
    cout<<e+4<<"个";//素数最后个数
        return 0;
    }

    展开全文
  •  * 题目:判断101-200之间有多少素数,并输出所有素数。  * 程序分析:  * (1)用一个数分别去除2到sqrt(这个数),如果能整除,则表明次数不是素数,反之是素数。  * (2)用2- n/2去除,因为一...
  • * 判断100-200之间有多少素数 并输出所有素数 * * 质数(prime number)又称素数无限个。 质数定义为在大于1的自然数中,除了1和它本身以外不再其他因数,这样的数称为质数。 * */ public class suShu { ...
  •  * 判断101-200之间有多少素数(又称质数(prime number)),并输出所有素数。  * 质数(prime number)又称素数无限个。一个大于1的自然数,除了1和它本身外,不能被其他自然数整除,  * 换句话说就是该数...
  • 判断101-200之间有多少素数,并输出所有素数。 只能被1和它本身整除的自然数为素数(质数) public class Prime { public void prime(int m,int n) { int count=0; for(;m&lt;n;m++) { boolean ...
  • 题目:判断101-200之间有多少素数,并输出所有素数。 分析: 质数(prime number)又称素数无限个。 质数定义为在大于1的自然数中,除了1和它本身以外不再其他因数。 即:只能被1和其本身整除。 Java...
  • //count用来存放一共有多少素数 int count = 0; //外层循环遍历101~200之间的数 for(int i=101;i&lt;=200;i++) { //term用来判断是否是素数 boolean term = true; //内层循环遍历当前数值能否被其他数整除 ...
  • public class question2 { public static void main(String[] args) { int count=0;...i=i+2) { //偶数不可能为素数 boolean a=true; for(int j=3;j<i;j++) { if(i%j0) { //只要存在一个因子就不是素...
  • 1. 判断101~200之间有多少素数? 1 package himi.hebao; 2 3 /** 4 * (1).编写函数isPrime()用来判断输入数据是否为素数 (2).遍历判断101~200之间的数据是否为素数,并且计数count 5 * 6 * @author ...
  • 题目:判断101-200之间有多少素数,并输出所有素数。 程序分析:判断素数的方法:用一个数分别去除2到sqrt(这个数),如果能被整除,则表明此数不是素数,反之是素数。 ...
  • 题目:判断 101-200 之间有多少素数,并输出所有的素数 素数是什么: 质数又称素数。一个大于1的自然数,除了1和它自身外,不能被其他自然数整除的数叫做质数;否则称为合数。 那么题目的答案如下: 代码: ...
  • 统计1到1000之间有多少素数,并输出素数。 ** 如何插入一段漂亮的代码片 去博客设置页面,选择一款你喜欢的代码片高亮样式,下面展示同样高亮的 代码片. @Test public void ningTest(){ //新建一个list集合用来...
  • 判断101-200之间有多少素数,并输出所有素数 public class Ex02prime { /* * 判断101-200之间有多少素数,并输出所有素数 *  * 素数只能被1和它本身整除的正整数,即数n都不能被2~sqrt(n)整除。 *  ...
  • 1、代码如下: // test.cpp : Defines the entry point for the.../* 判断101-200之间有多少素数,并输出所有素数。*/ #include "stdafx.h" #include #include using namespace std; int main(int argc, char* ar
  • 判断101-200之间有多少素数,并输出所有素数。 2.程序分析 判断素数的方法:用一个数分别去除2到sqrt(这个数),如果能被整除,则表明此数不是素数,反之是素数。 count = 0 leap = 1 from math import sqrt for m ...
  • #判断101-200之间有多少素数,并输出所有素数 #判断是否是质数 def is_prime(num):  #取中间数,如果不能被整除,就取整数  middle = num // 2  #从2到中间数,只要能被整除,就说明不是质数  for i...
  • 素数素数的定义:只能被1以及自身整除的数 ...count=0 #统计一共有几个素数 for i in range(101,201): #左闭右开,所以需到201才能取到200 for j in range(2,i): #2-i的范围保证了除数不是1以及本身...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 11,402
精华内容 4,560
关键字:

一共有多少质数