蓝桥杯算法提高VIP-素数求和（java代码 埃氏筛法找素数）

解题思路:

        找素数问题，直接无脑上埃氏筛法就行了。埃氏筛法详情如下，也可自行百度或直接看代码注释，注释较为详细。
        要得到自然数n以内的全部素数，必须把不大于的所有素数的倍数剔除，剩下的就是素数。

        给出要筛数值的范围n，找出以内的素数。先用2去筛，即把2留下，把2的倍数剔除掉；再用下一个质数，也就是3筛，把3留下，把3的倍数剔除掉；接下去用下一个质数5筛，把5留下，把5的倍数剔除掉；不断重复下去......。下面举一个实例，求25以内的素数。

        1、列出2以后的所有序列：

        2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

        2、标出序列中的第一个素数，也就是2，序列变成：

        2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

        3、将剩下序列中，划掉2的倍数，序列变成：

        2 3 5 7 9 11 13 15 17 19 21 23 25

        5、如果这个序列中最大数小于最后一个标出的素数的平方，那么剩下的序列中所有的数都是素数，否则回到第二步。为何是平方可以参照代码理解。

        本例中，因为25大于2的平方，我们返回第二步：

        6、剩下的序列中未遍历过的第一个素数是3，将主序列中3的倍数划掉，主序列变成：

        2 3 5 7 11 13 17 19 23 25

        7、最后标记的素数为3

        8、25仍然大于3的平方，所以我们还要返回第二步：

        9、序列中未遍历过的第一个素数是5，同样将序列中5的倍数划掉，主序列成了：

        2 3 5 7 11 13 17 19 23

        10、最后标记的素数为5

        11、因为23小于5的平方，跳出循环.

        结论：2到25之间的素数是：2 3 5 7 11 13 17 19 23。

注意事项:
        存储素数和的数据类型记得用长整型，不然会因为短整型的大小限制导致答案错误，只有67分，别问我怎么知道的。
参考代码:

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		boolean[] isCompositeNumber = new boolean[n+1];//建立合数表，因为java布尔值默认为false，故采取合数表，下标为true就代表对应下标为合数，0,1除外
		isCompositeNumber[0] = true;//0和1既不是质数也不是合数，故设其为true
		isCompositeNumber[1] = true;
		for (int i = 2; i <= n/i; i++) {//从0遍历到根号n即可，原因在内层循环注释中
			if (isCompositeNumber[i] == false) {
				for (int j = i * i; j <= n; j = j + i) {//如果i是质数，那就把小于n的i的倍数置为合数，j从i的i倍开始是因为i的2倍3倍等小于i的倍数在2和3的i倍时便已遍历过
					isCompositeNumber[j] = true;//所以如果i*i大于n的话就可以结束了，i*i大于n的话内层循环不会执行
				}
			}
		}
		long sum = 0;//注意用long，int最大数值不够到2000000位的质数和
		for (int i = 0; i < isCompositeNumber.length; i++) {//遍历合数表，是质数就加起来
			if (isCompositeNumber[i] == false) {
				sum = sum + i;
			}
		}
		System.out.println(sum);
	}
}