信手拈来 妙手偶得 » 日志 » 【原创】用位图法求N以内的是连续三个素数和，本身也为素数的数
【原创】用位图法求N以内的是连续三个素数和，本身也为素数的数
Junglesong 发表于 2008-06-28 16:46:47
package com.sitinspring;
/** *//**
* 求N以内的是连续三个素数和，本身也为素数的数
* @author sitinspring（junglesong@gmail.com）
* @since 2008-6-12 上午11:27:26
* @vsersion 1.00 创建 sitinspring 2008-6-12 上午11:27:26
*/
public class ContinuousPrimeSum2 
{
/** *//**
* n:数字上限
*/
private int n;
/** *//**
* 构造函数
* @param n
*/
public ContinuousPrimeSum2(int n){
this.n=n;
int[] arr=getPrimeZeroArray();
int[] continuousArr=getPrimeNumberArray(arr);
for(int i=0;i<continuousArr.length-2;i++){
int sum=continuousArr[i]+continuousArr[i+1]+continuousArr[i+2];
if(sum<n && arr[sum]!=0){
System.out.println(n+"以内是連續三個素數和，本身也為素數的數為："+sum+" 其子素數為："+continuousArr[i]+","+continuousArr[i+1]+","+continuousArr[i+2]);
}
}
}
/** *//**
* 取得素数和零的数组，合数位补零
* @param initialArr
* @return
*/
public int[] getPrimeZeroArray() {
// 初始数组，想在其中依次放入素数，其它位置为零
int[] arr = new int[n];
// 遍历2-100，如果是素数的话放入初始数组中
for (int i = 2; i < n; i++) {
if (isPrimeNumber(i)) {
// 是素数则放入初始数组中
arr[i] = i;
}
}
// 返回
return arr;
}
/** *//**
* 取得完全是素数的数组
* @param primeZeroArr
* @return
*/
public int[] getPrimeNumberArray(int[] primeZeroArr) {
// 得出返回数组的长度
int maxLength = 0;
for (int temp : primeZeroArr) {
maxLength+=temp>0?1:0;
}
// 定义返回的素数数组
int[] arr = new int[maxLength];
int index=0;
// 填值
for (int i = 0; i < primeZeroArr.length; i++) {
if(primeZeroArr[i]>0){
arr[index++] = primeZeroArr[i];
}
}
// 返回
return arr;
}
/** *//**
* 判断是否质数（素数）
* @param number
* @return
*/
private static boolean isPrimeNumber(int number) {
for (int i = 2; i < number / 2 + 1; i++) {
if (number % i == 0) {
return false;
}
}
return true;
}
/** *//**
* 程序入口
* @param args
*/
public static void main(String[] args) {
new ContinuousPrimeSum2(1000);
}
}
输出结果：
1000以内是連續三個素數和，本身也為素數的數為：23 其子素數為：5,7,11
1000以内是連續三個素數和，本身也為素數的數為：31 其子素數為：7,11,13
1000以内是連續三個素數和，本身也為素數的數為：41 其子素數為：11,13,17
1000以内是連續三個素數和，本身也為素數的數為：59 其子素數為：17,19,23
1000以内是連續三個素數和，本身也為素數的數為：71 其子素數為：19,23,29
1000以内是連續三個素數和，本身也為素數的數為：83 其子素數為：23,29,31
1000以内是連續三個素數和，本身也為素數的數為：97 其子素數為：29,31,37
1000以内是連續三個素數和，本身也為素數的數為：109 其子素數為：31,37,41
1000以内是連續三個素數和，本身也為素數的數為：131 其子素數為：41,43,47
1000以内是連續三個素數和，本身也為素數的數為：173 其子素數為：53,59,61
1000以内是連續三個素數和，本身也為素數的數為：199 其子素數為：61,67,71
1000以内是連續三個素數和，本身也為素數的數為：211 其子素數為：67,71,73
1000以内是連續三個素數和，本身也為素數的數為：223 其子素數為：71,73,79
1000以内是連續三個素數和，本身也為素數的數為：251 其子素數為：79,83,89
1000以内是連續三個素數和，本身也為素數的數為：269 其子素數為：83,89,97
1000以内是連續三個素數和，本身也為素數的數為：311 其子素數為：101,103,107
1000以内是連續三個素數和，本身也為素數的數為：349 其子素數為：109,113,127
1000以内是連續三個素數和，本身也為素數的數為：439 其子素數為：139,149,151
1000以内是連續三個素數和，本身也為素數的數為：457 其子素數為：149,151,157
1000以内是連續三個素數和，本身也為素數的數為：487 其子素數為：157,163,167
1000以内是連續三個素數和，本身也為素數的數為：503 其子素數為：163,167,173
1000以内是連續三個素數和，本身也為素數的數為：607 其子素數為：197,199,211
1000以内是連續三個素數和，本身也為素數的數為：661 其子素數為：211,223,227
1000以内是連續三個素數和，本身也為素數的數為：701 其子素數為：229,233,239
1000以内是連續三個素數和，本身也為素數的數為：829 其子素數為：271,277,281
1000以内是連續三個素數和，本身也為素數的數為：857 其子素數為：281,283,293
1000以内是連續三個素數和，本身也為素數的數為：883 其子素數為：283,293,307
1000以内是連續三個素數和，本身也為素數的數為：911 其子素數為：293,307,311
1000以内是連續三個素數和，本身也為素數的數為：941 其子素數為：311,313,317
/** *//** * 求N以内的是连续三个素数和，本身也为素数的数 * @author sitinspring（junglesong@gmail.com） * @since 2008-6-12 上午11:27:26 * @vsersion 1.00 创建 sitinspring 2008-6-12 上午11:27:26 */public class ContinuousPrimeSum2 { /** *//** * n:数字上限 */ private int n; /** *//** * 构造函数 * @param n */ public ContinuousPrimeSum2(int n){ this.n=n; int[] arr=getPrimeZeroArray(); int[] continuousArr=getPrimeNumberArray(arr); for(int i=0;i<continuousArr.length-2;i++){ int sum=continuousArr[i]+continuousArr[i+1]+continuousArr[i+2]; if(sum<n && arr[sum]!=0){ System.out.println(n+"以内是連續三個素數和，本身也為素數的數為："+sum+" 其子素數為："+continuousArr[i]+","+continuousArr[i+1]+","+continuousArr[i+2]); } } } /** *//** * 取得素数和零的数组，合数位补零 * @param initialArr * @return */ public int[] getPrimeZeroArray() { // 初始数组，想在其中依次放入素数，其它位置为零 int[] arr = new int[n]; // 遍历2-100，如果是素数的话放入初始数组中 for (int i = 2; i < n; i++) { if (isPrimeNumber(i)) { // 是素数则放入初始数组中 arr[i] = i; } } // 返回 return arr; } /** *//** * 取得完全是素数的数组 * @param primeZeroArr * @return */ public int[] getPrimeNumberArray(int[] primeZeroArr) { // 得出返回数组的长度 int maxLength = 0; for (int temp : primeZeroArr) { maxLength+=temp>0?1:0; } // 定义返回的素数数组 int[] arr = new int[maxLength]; int index=0; // 填值 for (int i = 0; i < primeZeroArr.length; i++) { if(primeZeroArr[i]>0){ arr[index++] = primeZeroArr[i]; } } // 返回 return arr; } /** *//** * 判断是否质数（素数） * @param number * @return */ private static boolean isPrimeNumber(int number) { for (int i = 2; i < number / 2 + 1; i++) { if (number % i == 0) { return false; } } return true; } /** *//** * 程序入口 * @param args */ public static void main(String[] args) { new ContinuousPrimeSum2(1000); }}输出结果：
1000以内是連續三個素數和，本身也為素數的數為：23 其子素數為：5,7,111000以内是連續三個素數和，本身也為素數的數為：31 其子素數為：7,11,131000以内是連續三個素數和，本身也為素數的數為：41 其子素數為：11,13,171000以内是連續三個素數和，本身也為素數的數為：59 其子素數為：17,19,231000以内是連續三個素數和，本身也為素數的數為：71 其子素數為：19,23,291000以内是連續三個素數和，本身也為素數的數為：83 其子素數為：23,29,311000以内是連續三個素數和，本身也為素數的數為：97 其子素數為：29,31,371000以内是連續三個素數和，本身也為素數的數為：109 其子素數為：31,37,411000以内是連續三個素數和，本身也為素數的數為：131 其子素數為：41,43,471000以内是連續三個素數和，本身也為素數的數為：173 其子素數為：53,59,611000以内是連續三個素數和，本身也為素數的數為：199 其子素數為：61,67,711000以内是連續三個素數和，本身也為素數的數為：211 其子素數為：67,71,731000以内是連續三個素數和，本身也為素數的數為：223 其子素數為：71,73,791000以内是連續三個素數和，本身也為素數的數為：251 其子素數為：79,83,891000以内是連續三個素數和，本身也為素數的數為：269 其子素數為：83,89,971000以内是連續三個素數和，本身也為素數的數為：311 其子素數為：101,103,1071000以内是連續三個素數和，本身也為素數的數為：349 其子素數為：109,113,1271000以内是連續三個素數和，本身也為素數的數為：439 其子素數為：139,149,1511000以内是連續三個素數和，本身也為素數的數為：457 其子素數為：149,151,1571000以内是連續三個素數和，本身也為素數的數為：487 其子素數為：157,163,1671000以内是連續三個素數和，本身也為素數的數為：503 其子素數為：163,167,1731000以内是連續三個素數和，本身也為素數的數為：607 其子素數為：197,199,2111000以内是連續三個素數和，本身也為素數的數為：661 其子素數為：211,223,2271000以内是連續三個素數和，本身也為素數的數為：701 其子素數為：229,233,2391000以内是連續三個素數和，本身也為素數的數為：829 其子素數為：271,277,2811000以内是連續三個素數和，本身也為素數的數為：857 其子素數為：281,283,2931000以内是連續三個素數和，本身也為素數的數為：883 其子素數為：283,293,3071000以内是連續三個素數和，本身也為素數的數為：911 其子素數為：293,307,3111000以内是連續三個素數和，本身也為素數的數為：941 其子素數為：311,313,317
收藏:
QQ书签
del.icio.us
订阅:
Google
抓虾