本文共 2317 字，大约阅读时间需要 7 分钟。

素数，又称为质数，是不能被1与本身以外的其他整数整除的整数。如2,3,5,7,11,13,17。其中2事为唯一的偶素数。

相反，如果能被1或者本身意外的整数整除，该整数被称为合数或者复合数。

那么什么叫全素组呢？

如果不大于指定整数n的三个素数之和仍为素数，则把这三个素数称为一个基于n的全素组。

例如，对于n = 15，素数3、5、11 = 19为素数，则3、5、11称为一个基于15的全素组。

设计思路:

首先我们需要排除偶素数，因为一个偶素数2与其他两个奇素数不可能为素数。

1) 使用试商法判别素数

即用奇数j(3~sqrt(i))逐个对i进行试商。

如果 i % j == 0,说明i不是素数

2) 设置素数检测数组

为方便素数检测，设置数组p[i]，对3n以内的整数i通过试商法给p[i]赋值:若i为素数，p[i] = 1,否则p[i] = 0。

同时设置q[i]将所有不大于n的奇素数依次存入q数组中,设共有w个不大于n的奇素数。

3) 枚举循环设计

由于任意三个素数不能相同，因而设置的i,j,k三重枚举循环的取值范围分别为:

i: 1~ w - 2

j: i + 1 ~ w -1

k: j + 1~ w

在循环中，令s = q[i] + q[j] + q[k]，如果sum为素数(p[s] = 1),则q[i],q[j],q[k]为一个全素组，使用count统计个数

4) 比较最大值

通过s与最大值max比较确定并记录最大全素组。

程序实现:

package cn.qblank.enumeration;import java.util.Scanner;/** * 全素组 * @author Administrator */public class Demo1 {	public static void main(String[] args) {		Scanner input = new Scanner(System.in);		System.out.println("请输入整数n:");		int n = input.nextInt();		//创建数组用于存储是否是素数 1表示是素数  2表示不是素数		int[] p = new int[3*n];		//将是否是素数的状态存入p数组		p = isPrime(n, p);		//统计素数的个数,并将素数存入q数组中		int w = 0;		int[] q = new int[n];		for (int i = 3; i <= n; i=i+2) {			if (p[i] == 1) {				w++;				q[w] = i;			}		}		//统计全素组的个数以及计算最大全素组并输出		countPrime(p, w, q);		input.close();	}	/**	 * 统计全素组的个数以及计算最大全素组	 */	public static void countPrime(int[] p, int w, int[] q) {		int count = 0;		int max = 0;		//定义最大的三个全素数组		int maxi = 0;		int maxj = 0;		int maxk = 0;		for (int i = 1; i <= w - 2; i++) {			for (int j = i+1; j <= w - 1; j++) {				for (int k = j + 1; k <= w; k++) {					int s = q[i] + q[j] + q[k];					if (p[s] == 1) {						//统计全素组的个数						count++;						//大于max,就把其和s赋值给max,同时记录其全素组各项值						if (s > max) {							max = s;							maxi = q[i];							maxj = q[j];							maxk = q[k];						}					}				}			}		}		System.out.println("共有"+ count + "个全素组!");		if (count > 0) {			System.out.println("一个最大全素组为:" + maxi + "+" + maxj + "+" + maxk + "=" + max);		}	}	/**	 * 3n表示三个小于n的数之和不大于3n  用于判断3n之类的数是否为素数，并将结果存入数组中	 * @param n 最大范围	 * @param p 存储3~3n之间是否是素数	 * @return	 */	public static int[] isPrime(int n, int[] p) {		for (int i = 3; i <= 3*n; i=i+2) {			//打一个标记flag,默认为素数			boolean flag = true;			//除数的最大数			int z = (int) Math.sqrt(i);			for (int j = 3; j <= z; j=j+2) {				//当不为素数时，将标记设置为false				if (i % j == 0) {					flag = false;					break;				}			}			//判断i是否为素数			if (flag) {				p[i] = 1;			}		}		return p;	}}