Fortunate numbers: Difference between revisions
m
→{{header|ALGOL 68}}: typo
m (→{{header|Wren}}: Minor tidy) |
m (→{{header|ALGOL 68}}: typo) |
||
| (2 intermediate revisions by 2 users not shown) | |||
Line 99:
239 271 277 283 293 307 311 313 331 353
373 379 383 397 401 409 419 421 439 443
</pre>
=={{header|ALGOL 68}}==
{{works with|ALGOL 68G|Any - tested with release 2.8.3.win32}}
Uses Algol 68G's LONG LONG INT which has programmer specifiable precision.<br/>
Some arbitrary limits are used here - only the first 100 primorials are considered and it is assumed that the first 50 Fortunate numbers are all under 500.<br/>
Also shows the primorial associated with the Fortunate numbers.
{{libheader|ALGOL 68-primes}}
The source of the ALGOL 68-primes library is on a separate Rosetta Code page - see the above link.
<syntaxhighlight lang="algol68">
BEGIN # find some Fortunate numbers m, m is smallest positive integer > 1 #
# where primorial(n) + m is prime for some n #
# as all primorials are even, m must be odd #
PR precision 2000 PR # set the number of digits for LONG LONG INT #
PR read "primes.incl.a68" PR # include prime utilities #
INT max fortunate = 500; # largeest fortunate number we will consider #
[]BOOL is prime = PRIMESIEVE 5 000;
[ 1 : max fortunate ]INT fortunate; FOR i TO max fortunate DO fortunate[ i ] := 0 OD;
INT primorial pos := 0;
LONG LONG INT primorial := 1;
INT prime pos := 0;
WHILE primorial pos < 100 DO
WHILE NOT is prime[ prime pos +:= 1 ] DO SKIP OD;
primorial pos +:= 1;
primorial *:= prime pos;
INT m := 3;
WHILE NOT is probably prime( primorial + m ) AND m <= max fortunate DO m +:= 2 OD;
IF m <= max fortunate THEN
IF fortunate[ m ] = 0 THEN fortunate[ m ] := primorial pos FI
FI
OD;
print( ( "The first 50 Fortunate numbers:", newline ) );
INT f count := 0;
FOR f TO max fortunate WHILE f count < 50 DO
IF fortunate[ f ] /= 0 THEN
print( ( whole( f, -5 ) ) );
IF ( f count +:= 1 ) MOD 10 = 0 THEN print( ( newline ) ) FI
FI
OD;
print( ( "The primorial associated with the first 50 Fortunate numbers:", newline ) );
f count := 0;
FOR f TO max fortunate WHILE f count < 50 DO
IF fortunate[ f ] /= 0 THEN
print( ( whole( fortunate[ f ], -5 ) ) );
IF ( f count +:= 1 ) MOD 10 = 0 THEN print( ( newline ) ) FI
FI
OD
END
</syntaxhighlight>
{{out}}
<pre>
The first 50 Fortunate numbers:
3 5 7 13 17 19 23 37 47 59
61 67 71 79 89 101 103 107 109 127
151 157 163 167 191 197 199 223 229 233
239 271 277 283 293 307 311 313 331 353
373 379 383 397 401 409 419 421 439 443
The primorial associated with the first 50 Fortunate numbers:
1 2 3 4 6 7 5 9 14 16
10 11 13 21 19 24 20 15 18 28
22 35 31 36 30 23 39 27 32 26
34 55 54 53 50 57 62 45 52 65
73 59 42 63 56 75 66 67 37 51
</pre>
Line 211 ⟶ 276:
239 271 277 283 293 307 311 313 331 353
373 379 383 397 401 409 419 421 439 443
</pre>
=={{header|C#}}==
{{trans|Java}}
<syntaxhighlight lang="C#">
using System;
using System.Collections.Generic;
using System.Numerics;
public class FortunateNumbers
{
private const int CERTAINTY_LEVEL = 10;
public static void Main(string[] args)
{
var primes = PrimeSieve(400);
SortedSet<int> fortunates = new SortedSet<int>();
BigInteger primorial = BigInteger.One;
foreach (var prime in primes)
{
primorial *= prime;
int candidate = 3;
while (!BigInteger.Add(primorial, candidate).IsProbablyPrime(CERTAINTY_LEVEL))
{
candidate += 2;
}
fortunates.Add(candidate);
}
Console.WriteLine("The first 50 distinct fortunate numbers are:");
int count = 0;
foreach (var fortunate in fortunates)
{
if (count >= 50) break;
Console.Write($"{fortunate,4}{(count % 10 == 9 ? "\n" : "")}");
count++;
}
}
private static List<int> PrimeSieve(int aNumber)
{
var sieve = new bool[aNumber + 1];
var primes = new List<int>();
for (int i = 2; i <= aNumber; i++)
{
if (!sieve[i])
{
primes.Add(i);
for (int j = i * i; j <= aNumber && j > 0; j += i)
{
sieve[j] = true;
}
}
}
return primes;
}
}
public static class BigIntegerExtensions
{
private static Random random = new Random();
public static bool IsProbablyPrime(this BigInteger source, int certainty)
{
if (source == 2 || source == 3)
return true;
if (source < 2 || source % 2 == 0)
return false;
BigInteger d = source - 1;
int s = 0;
while (d % 2 == 0)
{
d /= 2;
s += 1;
}
for (int i = 0; i < certainty; i++)
{
BigInteger a = RandomBigInteger(2, source - 2);
BigInteger x = BigInteger.ModPow(a, d, source);
if (x == 1 || x == source - 1)
continue;
for (int r = 1; r < s; r++)
{
x = BigInteger.ModPow(x, 2, source);
if (x == 1)
return false;
if (x == source - 1)
break;
}
if (x != source - 1)
return false;
}
return true;
}
private static BigInteger RandomBigInteger(BigInteger minValue, BigInteger maxValue)
{
if (minValue > maxValue)
throw new ArgumentException("minValue must be less than or equal to maxValue");
BigInteger range = maxValue - minValue + 1;
int length = range.ToByteArray().Length;
byte[] buffer = new byte[length];
BigInteger result;
do
{
random.NextBytes(buffer);
buffer[buffer.Length - 1] &= 0x7F; // Ensure non-negative
result = new BigInteger(buffer);
} while (result < minValue || result >= maxValue);
return result;
}
}
</syntaxhighlight>
{{out}}
<pre>
The first 50 distinct fortunate numbers are:
3 5 7 13 17 19 23 37 47 59
61 67 71 79 89 101 103 107 109 127
151 157 163 167 191 197 199 223 229 233
239 271 277 283 293 307 311 313 331 353
373 379 383 397 401 409 419 421 439 443
</pre>
| |||