Skip to content

Instantly share code, notes, and snippets.

@winse
Created May 31, 2014 09:56
Show Gist options
  • Save winse/3e77d6eeb7591e93efa5 to your computer and use it in GitHub Desktop.
Save winse/3e77d6eeb7591e93efa5 to your computer and use it in GitHub Desktop.
求单纯质因数的合数
package com.github.winse;
import java.util.Arrays;
import java.util.BitSet;
import java.util.LinkedList;
import java.util.List;
/**
*
* 单纯质因数的合数
*
* 具有互不相同的质因素的合数
*
* XXX 除以double质数,才是正道!
*/
public class PurePrime {
public static void main(String[] args) {
long start = System.currentTimeMillis();
int data = 100000;
System.out.println("获取 " + data + " 的纯质合数: ");
System.out.println();
new PurePrime().printPure(data);
long end = System.currentTimeMillis();
System.out.println();
System.out.println("整个过程耗时: " + (end - start) + " milliseconds");
}
private int count = 0;
private void print(Object data, boolean reset) {
System.out.print(data);
if (reset) {
count = 0;
}
}
private void print(Object data) {
print(data, false);
}
private void print(int data) {
if (count > 0 && (count % 20 == 0)) {
System.out.println();
}
count++;
print(data + "\t");
}
private List<Case> latestLevelPure;
public void printPure(int data) {
Integer[] primes = getPrime(data);
System.out.println("符合要求的质数有: " + Arrays.toString(primes));
BitSet pureData = new BitSet(data);
// 理论上组合的因子个数
int combination = 1;
while (combination <= primes.length) {
List<Case> results = fixNumArgs(data, primes, combination);
if (results != null)
for (Case cs : results) {
pureData.set(cs.value());
}
combination++;
}
for (int i = 0; i < data; i++) {
if (pureData.get(i)) {
print(i);
}
}
}
private List<Case> fixNumArgs(int data, Integer[] primes, int combination) {
List<Case> latestCases;
// 因子个数(M)在(M-1)个因子的基础上进行进行
if (combination == 1) {
latestCases = new LinkedList<Case>();
for (int i = 0; i < primes.length; i++) {
latestCases.add(new Case(primes[i], i));
}
} else {
latestCases = latestLevelPure;
}
if (latestCases == null || latestCases.size() == 0) {
return null;
}
List<Case> newCases = new LinkedList<>();
for (Case cs : latestCases) {
int index = cs.index() + 1;
for (; index < primes.length; index++) {
int np = primes[index];
int m = cs.multi(np);
if (m > 0 && m < data) {
Case newCase = cs.clone2();
newCase.add(np, index);
newCases.add(newCase);
} else {
break;
}
}
}
System.out.println(combination + " : size$" + String.valueOf(newCases.size()) + "=> "
+ (newCases.size() > 100 ? "" : Arrays.toString(newCases.toArray())));
return latestLevelPure = newCases;
}
static class Case implements Cloneable {
private int value = 1;
// 在质数列表中的位置,数字从零开始
private int index;
public Case(int data, int index) {
value *= data;
this.index = index;
}
public Case clone2() {
try {
return (Case) this.clone();
} catch (CloneNotSupportedException e) {
throw new RuntimeException(e);
}
}
@Override
public Object clone() throws CloneNotSupportedException {
return super.clone();
}
@Override
public String toString() {
return value + "[" + index + "]";
}
public Case add(int data, int index) {
value *= data;
this.index = index;
return this;
}
public int index() {
return this.index;
}
public int multi(int data) {
return this.value * data;
}
public int value() {
return value;
}
}
/**
* @see <a href="http://liugang594.iteye.com/blog/753399">求质数的方法</a>
*/
private Integer[] getPrime(int data) {
long start = System.currentTimeMillis();
List<Integer> list = new LinkedList<Integer>();
// TODO 可以考虑只存奇数
BitSet b = new BitSet(data + 1);// 用于记录是否为质数
int i;
for (i = 2; i <= data; i++) {
b.set(i); // 初始化
}
// 忽略 1
i = 2;
while (i * i <= data) {
if (b.get(i)) {
list.add(i);
// 清除所有i的倍数, 2i/3i/...
int k = 2 * i;
while (k <= data) {
b.clear(k);
k += i;
}
}
i++;
}
// 处理剩余没处理的
while (i <= data) {
if (b.get(i))
list.add(i);
i++;
}
long end = System.currentTimeMillis();
System.out.println("获取质数用时: " + (end - start) + " milliseconds");
return list.toArray(new Integer[0]);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment