Super-Poulet numbers: Difference between revisions
New post.
Thundergnat (talk | contribs) m (Remove draft tag. Draft for over a year, multiple implementations, little controversy) |
(New post.) |
||
Line 162:
Task example:<syntaxhighlight lang="j"> 20{. (#~ is_super_poulet) 1+i.1e5
341 1387 2047 2701 3277 4033 4369 4681 5461 7957 8321 10261 13747 14491 15709 18721 19951 23377 31417 31609</syntaxhighlight>
=={{header|Java}}==
<syntaxhighlight lang="java">
import java.util.Set;
import java.util.TreeSet;
public final class SuperPouletNumbers {
public static void main(String[] args) {
int n = 2;
int count = 0;
boolean searching = true;
while ( searching ) {
if ( isSuperPouletNumber(n) ) {
count += 1;
if ( count <= 20 ) {
System.out.print(String.format("%6d%s", n, ( count % 5 == 0 ? "\n" : " " )));
} else if ( n > 1_000_000 ) {
System.out.println(System.lineSeparator() +
"The first super-Poulet number greater than one million is " + n + " at index " + count);
searching = false;
}
}
n += 1;
}
}
private static boolean isSuperPouletNumber(int number) {
if ( isPrime(number) || modulusPower(2, number - 1, number) != 1 ) {
return false;
}
for ( int divisor : divisors(number) ) {
if ( modulusPower(2, divisor, divisor) != 2 ) {
return false;
}
}
return true;
}
// Return the divisors of the given number, excluding 1
private static Set<Integer> divisors(int number) {
Set<Integer> result = new TreeSet<Integer>();
for ( int d = 2; d * d <= number; d++ ) {
if ( number % d == 0 ) {
result.add(d);
result.add(number / d);
}
}
result.add(number);
return result;
}
private static long modulusPower(long base, long exponent, long modulus) {
if ( modulus == 1 ) {
return 0;
}
base %= modulus;
long result = 1;
while ( exponent > 0 ) {
if ( ( exponent & 1 ) == 1 ) {
result = ( result * base ) % modulus;
}
base = ( base * base ) % modulus;
exponent >>= 1;
}
return result;
}
private static boolean isPrime(int number) {
if ( number < 2 ) {
return false;
}
if ( number % 2 == 0 ) {
return number == 2;
}
if ( number % 3 == 0 ) {
return number == 3;
}
int delta = 2;
int k = 5;
while ( k * k <= number ) {
if ( number % k == 0 ) {
return false;
}
k += delta;
delta = 6 - delta;
}
return true;
}
}
</syntaxhighlight>
{{ out }}
<pre>
341 1387 2047 2701 3277
4033 4369 4681 5461 7957
8321 10261 13747 14491 15709
18721 19951 23377 31417 31609
The first super-Poulet number greater than one million is 1016801 at index 109
</pre>
=={{header|Julia}}==
| |||