Home primes: Difference between revisions
Content added Content deleted
(New post.) |
|||
Line 293: | Line 293: | ||
19 is prime |
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> |
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}}== |
=={{header|Julia}}== |