Ormiston triples: Difference between revisions
New post.
(Promoted to 'full' task.) |
(New post.) |
||
Line 864:
82324237 82523017 83279783 86050781 92514341
</syntaxhighlight>
=={{header|Java}}==
This example uses a segmented prime iterator to complete the stretch task in 75 seconds, without external libraries.
<syntaxhighlight lang="java">
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
public final class OrmistonTriples {
public static void main(String[] aArgs) {
final long limit = 10_000_000_000L;
SegmentedPrimeIterator primes = new SegmentedPrimeIterator(limit);
List<Long> ormistons = new ArrayList<Long>();
long lowerLimit = limit / 10;
int count = 0;
List<Integer> counts = new ArrayList<Integer>();
long p1 = 0, p2 = 0, p3 = 0;
while ( p3 < limit ) {
p1 = p2; p2 = p3; p3 = primes.next();
if ( ( p2 - p1 ) % 18 != 0 || ( p3 - p2 ) % 18 != 0 ) {
continue;
}
if ( ! haveSameDigits(p1, p2) ) {
continue;
}
if ( haveSameDigits(p2, p3) ) {
if ( count < 25 ) {
ormistons.add(p1);
}
if ( p1 >= lowerLimit ) {
counts.add(count);
lowerLimit *= 10;
}
count += 1;
}
}
counts.add(count);
System.out.println("The smallest members of the first 25 Ormiston triples:");
for ( int i = 0; i < ormistons.size(); i++ ) {
System.out.print(String.format("%10d%s", ormistons.get(i), ( i % 5 == 4 ? "\n" : "" )));
}
System.out.println();
lowerLimit = limit / 10;
for ( int i = 0; i < counts.size(); i++ ) {
System.out.println(counts.get(i) + " Ormiston triples less than " + lowerLimit);
lowerLimit *= 10;
}
}
private static boolean haveSameDigits(long aOne, long aTwo) {
return digits(aOne).equals(digits(aTwo));
}
private static List<Integer> digits(long aNumber) {
List<Integer> result = new ArrayList<Integer>();
while ( aNumber > 0 ) {
result.add((int) ( aNumber % 10 ));
aNumber /= 10;
}
Collections.sort(result);
return result;
}
}
final class SegmentedPrimeIterator {
public SegmentedPrimeIterator(long aLimit) {
squareRoot = (int) Math.sqrt(aLimit);
high = squareRoot;
smallSieve(squareRoot);
}
public long next() {
if ( index == primes.size() ) {
index = 0;
segmentedSieve();
}
return primes.get(index++);
}
private void segmentedSieve() {
low += squareRoot;
high += squareRoot;
boolean[] markedPrime = new boolean[squareRoot];
Arrays.fill(markedPrime, true);
for ( int i = 0; i < smallPrimes.size(); i++ ) {
long lowLimit = ( low / smallPrimes.get(i) ) * smallPrimes.get(i);
if ( lowLimit < low ) {
lowLimit += smallPrimes.get(i);
}
for ( long j = lowLimit; j < high; j += smallPrimes.get(i) ) {
markedPrime[(int) ( j - low )] = false;
}
}
primes.clear();
for ( long i = low; i < high; i++ ) {
if ( markedPrime[(int) ( i - low )] ) {
primes.add(i);
}
}
}
private void smallSieve(int aSquareRoot) {
boolean[] markedPrime = new boolean[aSquareRoot + 1];
Arrays.fill(markedPrime, true);
for ( int p = 2; p * p <= aSquareRoot; p++ ) {
if ( markedPrime[p] ) {
for ( int i = p * p; i <= aSquareRoot; i += p ) {
markedPrime[i] = false;
}
}
}
for ( int p = 2; p <= aSquareRoot; p++ ) {
if ( markedPrime[p] ) {
primes.add((long) p);
}
}
smallPrimes.addAll(primes);
}
private static int index, squareRoot;
private static long low, high;
private static List<Long> primes = new ArrayList<Long>();
private static List<Long> smallPrimes = new ArrayList<Long>();
}
</syntaxhighlight>
{{ out }}
<pre>
The smallest members of the first 25 Ormiston triples:
11117123 12980783 14964017 32638213 32964341
33539783 35868013 44058013 46103237 48015013
50324237 52402783 58005239 60601237 61395239
74699789 76012879 78163123 80905879 81966341
82324237 82523017 83279783 86050781 92514341
368 Ormiston triples less than 1000000000
4925 Ormiston triples less than 10000000000
</pre>
=={{header|Julia}}==
| |||