Ramanujan primes: Difference between revisions
Added completed solution in python
m (→{{header|Wren}}: Minor tidy) |
Didgeridoo52 (talk | contribs) (Added completed solution in python) |
||
| (2 intermediate revisions by 2 users not shown) | |||
Line 83:
The 10000th Ramanujan prime is: 242057
</pre>
=={{header|BASIC}}==
==={{header|FreeBASIC}}===
{{trans|Phix}}
<syntaxhighlight lang="vbnet">#define floor(x) ((x*2.0-0.5) Shr 1)
Dim Shared As Integer pi()
Sub primeCounter(limit As Integer)
Dim As Integer i, q, p, sq, total
Redim pi(limit)
pi(0) = 0
pi(1) = 0
For i = 2 To limit
pi(i) = 1
Next
If limit > 2 Then
For i = 4 To limit Step 2
pi(i) = 0
Next i
p = 3
sq = 9
While sq <= limit
If pi(p) <> 0 Then
For q = sq To limit Step p*2
pi(q) = 0
Next q
End If
sq += (p + 1) * 4
p += 2
Wend
total = 0
For i = 2 To limit
total += pi(i)
pi(i) = total
Next i
End If
End Sub
Function ramanujanMax(n As Integer) As Integer
Return floor(4 * n * Log(4*n))
End Function
Function ramanujanPrime(n As Integer) As Integer
Dim As Integer i, maxposs
If n = 1 Then Return 2
maxposs = ramanujanMax(n)
For i = maxposs - (maxposs Mod 2) To 1 Step -2
If pi(i) - pi(i\2) < n Then Return i + 1
Next i
Return 0
End Function
Dim As Integer p, n, limit = 1e6
Dim As Double t0 = Timer
primeCounter(ramanujanMax(limit))
Print "The first 100 Ramanujan primes are:"
For p = 1 To 100
Print Using " ####"; ramanujanPrime(p);
If p Mod 20 = 0 Then Print
Next p
Print
For p = 3 To 6
n = 10 ^ p
Print Using "The &th Ramanujan prime is &"; n; ramanujanPrime(n)
Next p
Print Using "##.##sec."; Timer - t0
Sleep</syntaxhighlight>
{{out}}
<pre>The first 100 Ramanujan primes are:
2 11 17 29 41 47 59 67 71 97 101 107 127 149 151 167 179 181 227 229
233 239 241 263 269 281 307 311 347 349 367 373 401 409 419 431 433 439 461 487
491 503 569 571 587 593 599 601 607 641 643 647 653 659 677 719 727 739 751 769
809 821 823 827 853 857 881 937 941 947 967 983 1009 1019 1021 1031 1049 1051 1061 1063
1087 1091 1097 1103 1151 1163 1187 1217 1229 1249 1277 1289 1297 1301 1367 1373 1423 1427 1429 1439
The 1000th Ramanujan prime is 19403
The 10000th Ramanujan prime is 242057
The 100000th Ramanujan prime is 2916539
The 1000000th Ramanujan prime is 34072993
1.53sec.</pre>
==={{header|Yabasic}}===
{{trans|FreeBASIC}}
<syntaxhighlight lang="vbnet">dim cnt(1e6)
primeCounter(ramanujanMax((1e6)))
print "The first 100 Ramanujan primes are:"
for p = 1 to 100
print ramanujanPrime(p) using ("#####");
if mod(p, 20) = 0 print
next p
print
for p = 3 to 6
n = 10 ^ p
print "The ", n, "th Ramanujan prime is ", ramanujanPrime(n)
next p
print peek("millisrunning") / 1000, "sec."
end
sub primeCounter(limit)
local i, q, p, sq, total
redim cnt(limit)
cnt(0) = 0
cnt(1) = 0
for i = 2 to limit
cnt(i) = 1
next
if limit > 2 then
for i = 4 to limit step 2
cnt(i) = 0
next i
p = 3
sq = 9
while sq <= limit
if cnt(p) <> 0 then
for q = sq to limit step p*2
cnt(q) = 0
next q
fi
sq = sq + (p + 1) * 4
p = p + 2
wend
total = 0
for i = 2 to limit
total = total + cnt(i)
cnt(i) = total
next i
fi
end sub
sub ramanujanMax(n)
return floor(4 * n * log(4*n))
end sub
sub ramanujanPrime(n)
local i, maxposs
if n = 1 return 2
maxposs = ramanujanMax(n)
for i = maxposs - mod(maxposs, 2) to 1 step -2
if cnt(i) - cnt(floor(i/2)) < n return i + 1
next i
return 0
end sub</syntaxhighlight>
{{out}}
<pre>The first 100 Ramanujan primes are:
2 11 17 29 41 47 59 67 71 97 101 107 127 149 151 167 179 181 227 229
233 239 241 263 269 281 307 311 347 349 367 373 401 409 419 431 433 439 461 487
491 503 569 571 587 593 599 601 607 641 643 647 653 659 677 719 727 739 751 769
809 821 823 827 853 857 881 937 941 947 967 983 1009 1019 1021 1031 1049 1051 1061 1063
1087 1091 1097 1103 1151 1163 1187 1217 1229 1249 1277 1289 1297 1301 1367 1373 1423 1427 1429 1439
The 1000th Ramanujan prime is 19403
The 10000th Ramanujan prime is 242057
The 100000th Ramanujan prime is 2916539
The 1000000th Ramanujan prime is 34072993
35.14sec.</pre>
=={{header|C++}}==
Line 262 ⟶ 420:
</pre>
=={{header|EasyLang}}==
{{trans|Go}}
<syntaxhighlight>
global cnt[] .
proc primcnt limit . .
cnt[] = [ 0 1 1 ]
for i = 4 step 2 to limit
cnt[] &= 0
cnt[] &= 1
.
p = 3
sq = 9
while sq <= limit
if cnt[p] <> 0
for q = sq step p * 2 to limit
cnt[q] = 0
.
.
sq += (p + 1) * 4
p += 2
.
for i = 2 to limit
sum += cnt[i]
cnt[i] = sum
.
.
func log n .
e = 2.7182818284590452354
return log10 n / log10 e
.
func ramamax n .
return floor (4 * n * log (4 * n))
.
func ramaprim n .
if n = 1
return 2
.
for i = ramamax n downto 2 * n
if i mod 2 = 0
if cnt[i] - cnt[i / 2] < n
return i + 1
.
.
.
return 0
.
primcnt (1 + ramamax 1000)
print "The first 100 Ramanujan primes are:"
for i = 1 to 100
write ramaprim i & " "
.
print ""
print ""
print "The 1000th Ramanujan prime is " & ramaprim 1000
</syntaxhighlight>
=={{header|F_Sharp|F#}}==
Line 830 ⟶ 1,044:
</pre>
<small>The last line is omitted under pwa/p2js since the primeCounter array is too much for Javascript to handle.</small>
=={{header|Python}}==
{{trans|Java}}
<syntaxhighlight lang="python">
import time
import math
class PrimeCounter:
"""Generate a list 'count' where count[n] is the number of primes less than or equal to n"""
def __init__(self, limit):
self.count = [1] * limit
count = self.count
if limit > 0:
count[0] = 0
if limit > 1:
count[1] = 0
for i in range(4, limit, 2):
count[i] = 0
p = 3
while p**2 < limit:
if count[p] != 0:
q = p**2
while q < limit:
count[q] = 0
q += p * 2
p += 2
for i, j in enumerate(count):
if i == 0:
continue
count[i] += count[i - 1]
def prime_count(self, n):
"""Get the number of primes less than or equal to n"""
if n > 0:
return self.count[n]
return 0
def ramanujan_prime_upper_bound(n):
"""Calculate the largest number the nth Ramanujan number could possibly be"""
return math.ceil(4 * n * math.log(4 * n))
def ramanujan_prime(prime_counter_in, n):
"""Generate the nth Ramanujan prime by finding the largest number 'i' where less than n primes are in the
range i//2 and i - the Ramanujan prime is one more than i"""
pci = prime_counter_in
for i in range(ramanujan_prime_upper_bound(n), -1, -1):
pi_n = pci.prime_count(i)
pi_half_n = pci.prime_count(i // 2)
if pi_n - pi_half_n < n:
return i + 1
return 0
def print_ramanujan_primes_in_range(start_number, end_number, prime_counter_in):
"""Print all Ramanujan primes between start_number (inclusive) and end_number (exclusive)"""
for i in range(start_number, end_number):
p = ramanujan_prime(prime_counter_in, i)
print(f"{p : <4}", end=" ")
if i % 10 == 0:
print()
def solve():
"""Return the first 100 Ramanujan primes and the 1000th, 10000th & 100000th Ramanujan primes"""
print("First 100 Ramanujan primes:\n")
largest_number_to_calculate = ramanujan_prime_upper_bound(100000) + 1
prime_counter = PrimeCounter(largest_number_to_calculate)
print_ramanujan_primes_in_range(1, 101, prime_counter)
print()
for number in (1_000, 10_000, 100_000):
answer = ramanujan_prime(prime_counter, number)
print(
f"The {number : >6}th ramanujan prime is {answer : >7}"
)
start = time.perf_counter()
solve()
end = time.perf_counter()
time_taken_ms = int((end - start) * 1000)
print(f"\nElapsed time: {time_taken_ms}ms")</syntaxhighlight>
{{out}}
<pre>
First 100 Ramanujan primes:
2 11 17 29 41 47 59 67 71 97
101 107 127 149 151 167 179 181 227 229
233 239 241 263 269 281 307 311 347 349
367 373 401 409 419 431 433 439 461 487
491 503 569 571 587 593 599 601 607 641
643 647 653 659 677 719 727 739 751 769
809 821 823 827 853 857 881 937 941 947
967 983 1009 1019 1021 1031 1049 1051 1061 1063
1087 1091 1097 1103 1151 1163 1187 1217 1229 1249
1277 1289 1297 1301 1367 1373 1423 1427 1429 1439
The 1000th ramanujan prime is 19403
The 10000th ramanujan prime is 242057
The 100000th ramanujan prime is 2916539
Elapsed time: 1460ms
</pre>
=={{header|Raku}}==
| |||