我们正在进行以下编程练习:Primes in numbers .
任务是计算正数的质因数分解。
首先我们写了:
import java.util.*;
import java.math.*;
public class PrimeDecomp {
public static String factors(int n) {
System.out.println("\n\\n\n\n\n\n\n\n\nn: "+n);
Map<Integer,Integer> map = new TreeMap<>();
for(int i=1; n>1 && i<(n/2); i=1){
System.out.println("out i: "+i);
int prime = nextPrime(i);
System.out.println("out prime: "+prime);
while(n%prime!=0){
i=prime;
System.out.println("in i: "+i);
prime = nextPrime(i);
System.out.println("in prime: "+prime);
}
n=n/prime;
int count = map.containsKey(prime) ? map.get(prime) : 0;
map.put(prime, count+1);
System.out.println("map: "+map);
System.out.println("\n\n\n\nnew n: "+n);
}
StringBuilder result = new StringBuilder();
for(Map.Entry<Integer,Integer> entry : map.entrySet()){
String text = entry.getValue()>1 ? String.format("(%d**%d)",entry.getKey(),entry.getValue()) : String.format("(%d)",entry.getKey());
result.append(text);
}
System.out.println("result: "+result);
return result.toString();
}
public static int nextPrime(int n){
BigInteger b = BigInteger.valueOf(n);
return Integer.parseInt(b.nextProbablePrime().toString());
}
}
当我们用 n = 35791357 测试前面的代码时,它耗尽了时间(执行时间超过 16000 毫秒)
我们决定使用另一种方法,不是每次迭代计算素数,而是一次计算所有素数,直到 n,如下所示:
import java.util.*;
import java.math.*;
public class PrimeDecomp {
public static String factors(int n) {
//System.out.println("\n\n\n\n\n\n\n\n\nn: "+n+"\n");
Map<Integer,Integer> map = new TreeMap<>();
List<Integer> primes = sieveOfEratosthenes(n);
//System.out.println("primes: "+primes);
for(int i=0; n>1 && i<(n/2); i=0){
//System.out.println("out i: "+i);
int prime = primes.get(i);
//System.out.println("out prime: "+prime);
while(n%prime!=0){
prime = primes.get(++i);
//System.out.println("in i: "+i);
//System.out.println("in prime: "+prime);
}
n=n/prime;
int count = map.containsKey(prime) ? map.get(prime) : 0;
map.put(prime, count+1);
//System.out.println("map: "+map);
//System.out.println("\n\n\n\nnew n: "+n);
}
StringBuilder result = new StringBuilder();
for(Map.Entry<Integer,Integer> entry : map.entrySet()){
String text = entry.getValue()>1 ? String.format("(%d**%d)",entry.getKey(),entry.getValue()) : String.format("(%d)",entry.getKey());
result.append(text);
}
System.out.println("result: "+result);
return result.toString();
}
public static List<Integer> sieveOfEratosthenes(int n){
boolean prime[] = new boolean[n+1];
Arrays.fill(prime,true);
for(int p=2; p*p<=n; p++){
if(prime[p]){
for(int i=p*2; i<=n; i+=p){
prime[i]=false;
}
}
}
List<Integer> primeNumbers = new LinkedList<>();
for(int i=2; i<=n; i++){
if(prime[i]){
primeNumbers.add(i);
}
}
return primeNumbers;
}
}
测试新代码后,我们观察到当 n = 933555431 时,执行超时。
我们考虑缓存上一次执行计算出的素数,这样算法就只需要计算上一次执行和新n之间的素数即可。
可以用伪代码解释为:
cachedPrimes = Create a static list to hold the calculated primes
primesCalculated = Create a static int to save until what n primes have been calculated
if primesCalculated < n
cachedPrimes = Get the primes list from primesCalculated to n
primesCalculated = n
我们开始起草代码如下:
import java.util.*;
import java.math.*;
public class PrimeDecomp {
static List<Integer> cachedPrimes = new ArrayList<>();
static int primesCalculated = 0;
public static String factors(int n) {
//System.out.println("\n\n\n\n\n\n\n\n\nn: "+n+"\n");
Map<Integer,Integer> map = new TreeMap<>();
List<Integer> primes = cachedPrimes;
if(primesCalculated<n){
if(primesCalculated==0){
primes.addAll(sieveOfEratosthenes(2,n));
}else{
int diff = n - primesCalculated;
primes.addAll(sieveOfEratosthenes(diff,n));
}
cachedPrimes = new ArrayList<Integer>(primes);
primesCalculated = n;
}
//System.out.println("primes: "+primes);
for(int i=0; i < primes.size() && n>1; i=0){
//System.out.println("out i: "+i);
int prime = primes.get(i);
//System.out.println("out prime: "+prime);
while(i < primes.size()-1 && n%prime!=0){
prime = primes.get(++i);
//System.out.println("in i: "+i);
//System.out.println("in prime: "+prime);
}
n=n/prime;
int count = map.containsKey(prime) ? map.get(prime) : 0;
map.put(prime, count+1);
//System.out.println("map: "+map);
//System.out.println("\n\n\n\nnew n: "+n);
}
StringBuilder result = new StringBuilder();
for(Map.Entry<Integer,Integer> entry : map.entrySet()){
String text = entry.getValue()>1 ? String.format("(%d**%d)",entry.getKey(),entry.getValue()) : String.format("(%d)",entry.getKey());
result.append(text);
}
//System.out.println("result: "+result);
return result.toString();
}
public static List<Integer> sieveOfEratosthenes(int from, int to){
boolean prime[] = new boolean[to+1];
Arrays.fill(prime,true);
for(int p=from; p*p<=to; p++){
if(prime[p]){
for(int i=p*2; i<=to; i+=p){
prime[i]=false;
}
}
}
List<Integer> primeNumbers = new LinkedList<>();
for(int i=from; i<=to; i++){
if(prime[i]){
primeNumbers.add(i);
}
}
return primeNumbers;
}
}
我们在尝试理解代码行为时遇到了困难。当我们执行练习的测试时,我们会看到:
“预期:61140377”,但实际是:933555431”
如果我们手动执行如下,n=61140377,它会通过:
import static org.junit.Assert.*;
import org.junit.*;
public class PrimeDecompTest {
@Test
public void testPrimeDecompOne() {
int lst = 7775460;
assertEquals(
"(2**2)(3**3)(5)(7)(11**2)(17)",
PrimeDecomp.factors(lst));
lst = 61140377;
assertEquals(
"(61140377)",
PrimeDecomp.factors(lst));
}
}
我们认为这是由于静态的cachedPrimes列表造成的。我们如何改进代码以缩短其执行时间并通过测试?
我们已阅读:
- https://www.baeldung.com/java-generate-prime-numbers
- https://www.geeksforgeeks.org/quick-ways-to-check-for-prime-and-find-next-prime-in-java/
- Java BigInteger prime numbers
- https://www.tutorialspoint.com/java/math/biginteger_probableprime.htm
- Converting from Integer, to BigInteger
- https://www.geeksforgeeks.org/biginteger-subtract-method-in-java-with-examples/
- Most efficient way to increment a Map value in Java
- Converting from Integer, to BigInteger
- How to sort Map values by key in Java?
- How do I efficiently iterate over each entry in a Java Map?
- Optimal way to find next prime number (Java)
- How do I join two lists in Java?
- https://www.geeksforgeeks.org/how-to-clone-a-list-in-java/
最佳答案
使用以下事实:
如果n
不是质数,那么它有一个除数 d
这样d*d <= n
.
for (int divisor = 2; n > 1; ++divisor) {
if (divisor * divisor >= n) {
// n is prime, we have n**1 here
break;
}
if (n % divisor == 0) {
// divisor is a prime factor, divide n by it while we can
int cnt = 0;
while (n % divisor == 0) {
n /= divisor;
++cnt;
}
// we have divisor**cnt here
}
}
更新:该算法的复杂度为O(sqrt (n))
关于java - 改进计算素因子分解的算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/61154120/