Wieferich primes: Difference between revisions
Content added Content deleted
(→{{header|Phix}}: added alternative, theoretically much faster) |
(Added Java and Swift solutions) |
||
Line 164: | Line 164: | ||
5000 wieferich_primes |
5000 wieferich_primes |
||
bye</lang> |
bye</lang> |
||
{{out}} |
|||
<pre> |
|||
Wieferich primes less than 5000: |
|||
1093 |
|||
3511 |
|||
</pre> |
|||
=={{header|Java}}== |
|||
{{trans|C++}} |
|||
<lang java>import java.util.*; |
|||
public class WieferichPrimes { |
|||
public static void main(String[] args) { |
|||
final int limit = 5000; |
|||
System.out.printf("Wieferich primes less than %d:\n", limit); |
|||
for (Integer p : wieferichPrimes(limit)) |
|||
System.out.println(p); |
|||
} |
|||
private static boolean[] primeSieve(int limit) { |
|||
boolean[] sieve = new boolean[limit]; |
|||
Arrays.fill(sieve, true); |
|||
if (limit > 0) |
|||
sieve[0] = false; |
|||
if (limit > 1) |
|||
sieve[1] = false; |
|||
for (int i = 4; i < limit; i += 2) |
|||
sieve[i] = false; |
|||
for (int p = 3; ; p += 2) { |
|||
int q = p * p; |
|||
if (q >= limit) |
|||
break; |
|||
if (sieve[p]) { |
|||
int inc = 2 * p; |
|||
for (; q < limit; q += inc) |
|||
sieve[q] = false; |
|||
} |
|||
} |
|||
return sieve; |
|||
} |
|||
private static long modpow(long base, long exp, long mod) { |
|||
if (mod == 1) |
|||
return 0; |
|||
long result = 1; |
|||
base %= mod; |
|||
for (; exp > 0; exp >>= 1) { |
|||
if ((exp & 1) == 1) |
|||
result = (result * base) % mod; |
|||
base = (base * base) % mod; |
|||
} |
|||
return result; |
|||
} |
|||
private static List<Integer> wieferichPrimes(int limit) { |
|||
boolean[] sieve = primeSieve(limit); |
|||
List<Integer> result = new ArrayList<>(); |
|||
for (int p = 2; p < limit; ++p) { |
|||
if (sieve[p] && modpow(2, p - 1, p * p) == 1) |
|||
result.add(p); |
|||
} |
|||
return result; |
|||
} |
|||
}</lang> |
|||
{{out}} |
{{out}} |
||
Line 293: | Line 358: | ||
println!("{}", p); |
println!("{}", p); |
||
} |
} |
||
}</lang> |
|||
{{out}} |
|||
<pre> |
|||
Wieferich primes less than 5000: |
|||
1093 |
|||
3511 |
|||
</pre> |
|||
=={{header|Swift}}== |
|||
{{trans|C++}} |
|||
<lang swift>func primeSieve(limit: Int) -> [Bool] { |
|||
guard limit > 0 else { |
|||
return [] |
|||
} |
|||
var sieve = Array(repeating: true, count: limit) |
|||
sieve[0] = false |
|||
if limit > 1 { |
|||
sieve[1] = false |
|||
} |
|||
if limit > 4 { |
|||
for i in stride(from: 4, to: limit, by: 2) { |
|||
sieve[i] = false |
|||
} |
|||
} |
|||
var p = 3 |
|||
while true { |
|||
var q = p * p |
|||
if q >= limit { |
|||
break |
|||
} |
|||
if sieve[p] { |
|||
let inc = 2 * p |
|||
while q < limit { |
|||
sieve[q] = false |
|||
q += inc |
|||
} |
|||
} |
|||
p += 2 |
|||
} |
|||
return sieve |
|||
} |
|||
func modpow(base: Int, exponent: Int, mod: Int) -> Int { |
|||
if mod == 1 { |
|||
return 0 |
|||
} |
|||
var result = 1 |
|||
var exp = exponent |
|||
var b = base |
|||
b %= mod |
|||
while exp > 0 { |
|||
if (exp & 1) == 1 { |
|||
result = (result * b) % mod |
|||
} |
|||
b = (b * b) % mod |
|||
exp >>= 1 |
|||
} |
|||
return result |
|||
} |
|||
func wieferichPrimes(limit: Int) -> [Int] { |
|||
let sieve = primeSieve(limit: limit) |
|||
var result: [Int] = [] |
|||
for p in 2..<limit { |
|||
if sieve[p] && modpow(base: 2, exponent: p - 1, mod: p * p) == 1 { |
|||
result.append(p) |
|||
} |
|||
} |
|||
return result |
|||
} |
|||
let limit = 5000 |
|||
print("Wieferich primes less than \(limit):") |
|||
for p in wieferichPrimes(limit: limit) { |
|||
print(p) |
|||
}</lang> |
}</lang> |
||