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 找出质数
 
作者: 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;
}

质数（素数），指在大于 1 的自然数中，除了 1 和该数自身外，无法被其他自然数整除的数（如 2，3，5，7，11 ……）。那么，如何能简单快速地找出质数呢？
 
埃拉托斯特尼筛法
 
 
埃拉托斯特尼（Eratosthenes）是一位古希腊数学家、地理学家、历史学家、诗人、天文学家，也是阿基米德的好基友。除了发明质数的筛选方法，他还测量地球周长、日地间距、地月间距，编排星图，绘制地图，把名字写在月球上（埃拉托斯特尼陨石坑）。
 
 
 
埃拉托斯特尼筛法（sieve of Eratosthenes ）用来找出一定范围（n）内的所有质数。其方法是从 2 开始，在$\sqrt{n}$ 以内，将每个质数的倍数剔除掉，剩下的就是所求范围的质数。例如找 100 以内的质数，先把 2 的倍数筛掉（保留 2），再把 3 的倍数筛掉（保留 3），如此重复下去，直到 7 的倍数被筛掉（因为下一个质数 11 已经大于$\sqrt{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 / 函数
Go
Python / primesieve
10万
9592
0.09s
0.07s
0.10s
0.006s
0.03s
100万
78498
0.6s
0.3s
0.25s
0.01s
0.04s
1000万
664579
6.1s
3.7s
2.6s
0.10s
0.11s
1亿
5761455
1m7s
54s
26s
1.6s
0.54s
10亿
50847534
算了吧
压力太大
太难了
15s
4.5s
20亿
98222287
32s
10s
30亿
144449537
53s
24s
40亿
189961812
1m17s
44s
50亿
234954223
1m49s
1m1s
60亿
279545368
2m31s
1m25s
100亿
455052511
>100m
以下用 count_primes(n)
2s
200亿
882206716
楼上…
5s
300亿
1300005926
8s
400亿
1711955433
11s
500亿
2119654578
14s
1000亿
4118054813
30s
（完）

 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+"个素数");
 }
 
 
 }