Home primes: Difference between revisions
New post.
(New post.) |
|||
Line 293:
19 is prime
HP20(15) = HP225(14) = HP3355(13) = HP51161(12) = HP114651(11) = HP3312739(10) = HP17194867(9) = HP194122073(8) = HP709273797(7) = HP39713717791(6) = HP113610337981(5) = HP733914786213(4) = HP3333723311815403(3) = HP131723655857429041(2) = HP772688237874641409(1) = 3318308475676071413 is prime</pre>
=={{header|Java}}==
<syntaxhighlight lang="java">
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.BitSet;
import java.util.Collections;
import java.util.List;
import java.util.concurrent.ThreadLocalRandom;
import java.util.stream.Collectors;
import java.util.stream.Stream;
public final class HomePrimes {
public static void main(String[] aArgs) {
listPrimes(PRIME_LIMIT);
List<Integer> values = List.of( 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 65 );
for ( int value : values ) {
BigInteger number = BigInteger.valueOf(value);
List<BigInteger> previousNumbers = Stream.of( number ).collect(Collectors.toList());
boolean searching = true;
while ( searching ) {
number = concatenate(primeFactors(number));
previousNumbers.add(number);
if ( number.isProbablePrime(CERTAINTY_LEVEL) ) {
final int lastIndex = previousNumbers.size() - 1;
for ( int k = lastIndex; k >= 1; k-- ) {
System.out.print("HP" + previousNumbers.get(lastIndex - k) + "(" + k + ") = ");
}
System.out.println(previousNumbers.get(lastIndex));
searching = false;
}
}
}
}
private static List<BigInteger> primeFactors(BigInteger aNumber) {
List<BigInteger> result = new ArrayList<BigInteger>();
if ( aNumber.compareTo(BigInteger.valueOf(PRIME_LIMIT * PRIME_LIMIT)) <= 0 ) {
return smallPrimeFactors(aNumber);
}
if ( aNumber.isProbablePrime(CERTAINTY_LEVEL) ) {
result.add(aNumber);
return result;
}
BigInteger divisor = pollardRho(aNumber);
result.addAll(primeFactors(divisor));
aNumber = aNumber.divide(divisor);
result.addAll(primeFactors(aNumber));
Collections.sort(result);
return result;
}
private static List<BigInteger> smallPrimeFactors(BigInteger aNumber) {
int number = aNumber.intValueExact();
List<BigInteger> result = new ArrayList<BigInteger>();
for ( int i = 0; i < primes.size() && number > 1; i++ ) {
while ( number % primes.get(i) == 0 ) {
result.add(BigInteger.valueOf(primes.get(i)));
number /= primes.get(i);
}
}
if ( number > 1 ) {
result.add(BigInteger.valueOf(number));
}
return result;
}
private static BigInteger pollardRho(BigInteger aNumber) {
if ( ! aNumber.testBit(0) ) {
return BigInteger.TWO;
}
final BigInteger constant = new BigInteger(aNumber.bitLength(), RANDOM);
BigInteger x = new BigInteger(aNumber.bitLength(), RANDOM);
BigInteger y = x;
BigInteger divisor = null;
do {
x = x.multiply(x).add(constant).mod(aNumber);
y = y.multiply(y).add(constant).mod(aNumber);
y = y.multiply(y).add(constant).mod(aNumber);
divisor = x.subtract(y).gcd(aNumber);
} while ( divisor.compareTo(BigInteger.ONE) == 0 );
return divisor;
}
private static BigInteger concatenate(List<BigInteger> aList) {
String number = aList.stream().map(String::valueOf).collect(Collectors.joining());
return new BigInteger(number);
}
public static void listPrimes(int aNumber) {
BitSet sieve = new BitSet(aNumber + 1);
sieve.set(2, aNumber + 1);
for ( int i = 2; i <= Math.sqrt(aNumber); i = sieve.nextSetBit(i + 1) ) {
for ( int j = i * i; j <= aNumber; j = j + i ) {
sieve.clear(j);
}
}
primes = new ArrayList<Integer>(sieve.cardinality());
for ( int i = 2; i >= 0; i = sieve.nextSetBit(i + 1) ) {
primes.add(i);
}
}
private static List<Integer> primes;
private static final int CERTAINTY_LEVEL = 20;
private static final int PRIME_LIMIT = 10_000;
private static final ThreadLocalRandom RANDOM = ThreadLocalRandom.current();
}
</syntaxhighlight>
{{ out }}
<pre>
HP2(1) = 2
HP3(1) = 3
HP4(2) = HP22(1) = 211
HP5(1) = 5
HP6(1) = 23
HP7(1) = 7
HP8(13) = HP222(12) = HP2337(11) = HP31941(10) = HP33371313(9) = HP311123771(8) = HP7149317941(7) = HP22931219729(6) = HP112084656339(5)
= HP3347911118189(4) = HP11613496501723(3) = HP97130517917327(2) = HP531832651281459(1) = 3331113965338635107
HP9(2) = HP33(1) = 311
HP10(4) = HP25(3) = HP55(2) = HP511(1) = 773
HP11(1) = 11
HP12(1) = 223
HP13(1) = 13
HP14(5) = HP27(4) = HP333(3) = HP3337(2) = HP4771(1) = 13367
HP15(4) = HP35(3) = HP57(2) = HP319(1) = 1129
HP16(4) = HP2222(3) = HP211101(2) = HP3116397(1) = 31636373
HP17(1) = 17
HP18(1) = 233
HP19(1) = 19
HP20(15) = HP225(14) = HP3355(13) = HP51161(12) = HP114651(11) = HP3312739(10) = HP17194867(9) = HP194122073(8) = HP709273797(7) = HP39713717791(6)
= HP113610337981(5) = HP733914786213(4) = HP3333723311815403(3) = HP131723655857429041(2) = HP772688237874641409(1) = 3318308475676071413
HP65(19) = HP513(18) = HP33319(17) = HP1113233(16) = HP11101203(15) = HP332353629(14) = HP33152324247(13) = HP3337473732109(12) = HP111801316843763(11)
= HP151740406071813(10) = HP31313548335458223(9) = HP3397179373752371411(8) = HP157116011350675311441(7) = HP331333391143947279384649(6)
= HP11232040692636417517893491(5) = HP711175663983039633268945697(4) = HP292951656531350398312122544283(3) = HP2283450603791282934064985326977(2)
= HP333297925330304453879367290955541(1) = 1381321118321175157763339900357651
</pre>
=={{header|Julia}}==
| |||