Ormiston triples: Difference between revisions
m
→{{header|Phix}}: use pygments
m (→{{header|Phix}}: use pygments) |
|||
Line 1,955:
=={{header|Phix}}==
<!--
<syntaxhighlight lang="phix">
--
-- demo\rosetta\Ormiston_triplets.exw
-- ==================================
--
-- Uses a segmented sieve, which is about half the speed of get_primes_le(), but uses far less memory.
-- If permited, get_primes_le(1e10) would generate a result of 455,052,511 primes, more than 32 bit
-- whereas this processes them on-the-fly, and only uses about 6MB of memory (ie 0.1% of 6GB).
--
with javascript_semantics
atom t0 = time()
procedure ormiston_triplets(atom limit)
// Generate primes using the segmented sieve of Eratosthenes.
// credit: https://gist.github.com/kimwalisch/3dc39786fab8d5b34fee
integer segment_size = floor(sqrt(limit)),
count = 0, i = 3, s = 3, triplen = 1
atom p1 = 2, p2, n = 3, nc = min(1e9,limit), low = 0, t1 = time()+1
sequence isprime = repeat(true,segment_size+1),
primes = {},
multiples = {},
orm25 = repeat(0,25)
while low<=limit do
sequence sieve = repeat(true,segment_size+1)
if time()>t1 then
progress("Processing %,d/%,d (%3.2f%%)\r",{low,limit,(low/limit)*100})
t1 = time()+1
end if
// current segment = [low, high]
atom high = min(low+segment_size,limit)
// generate sieving primes using simple sieve of Eratosthenes
while i*i<=min(high,segment_size) do
if isprime[i+1] then
for j=i*i to segment_size by i do
end if
i += 2
end while
// initialize sieving primes for segmented sieve
while s*s<=high do
if isprime[s+1] then
primes &= s
multiples &= s*s-low
end if
s += 2
end while
// sieve the current segment
for mi,j in multiples do
integer k = primes[mi]*2
while j<segment_size do
sieve[j+1] = false
j += k
end while
multiples[mi] = j - segment_size
end for
while n<=high do
if sieve[n-low+1] then // n is a prime
if triplen=1 then
if remainder(n-p1,18)=0
and sort(sprint(p1))=sort(sprint(n)) then
p2 = n
else
end if
elsif triplen=2
and remainder(n-p2,18)=0
and
-- triplet found!
if p1>=nc then
string e = elapsed_short(time()-t0)
progress("%,d
end if
count += 1
if count<=25 then
orm25[count] = sprintf("%d",{p1})
if count=25 then
end if
-- overlapping (and leave triplen set to 2):
p1 = p2
p2 = n
else
p1 = n
end if
n += 2
end while
low += segment_size
end while
string e = elapsed_short(time()-t0)
progress("%,d Ormiston triplets before %,d (%s)\n", {count, nc, e})
end procedure
ormiston_triplets(iff(platform()=JS?1e8:1e9))
</syntaxhighlight>
{{out}}
With limit upped to 1e10
Line 2,081 ⟶ 2,082:
=== faster version (win64 only) ===
Uses that primesieve dll I found, almost no memory at all, like less than 10MB, and is over twelve times faster than the above.
<!--
<syntaxhighlight lang="phix">
requires("1.0.3")
requires(WINDOWS)
requires(64,true)
include builtins/primesieve.e
atom t0 = time(), t1 = time()+1,
p = primesieve_next_prime(),
p1 = p, p2, count = 0, nc = 1e9
sequence orm25 = repeat(0,25)
procedure showt()
if count=25 then
progress("Smallest members of first 25 Ormiston triplets:\n")
progress("%s\n",join_by(orm25,1,5))
else
string e = elapsed_short(time()-t0)
progress("%,6d Ormiston triplets before %,d (%s)\n",{count,nc,e})
nc *= 10
end if
end procedure
while p<1e10 do
p2 = p1
p1 = p
p = primesieve_next_prime()
if remainder(p-p1,18)=0
and remainder(p1-p2,18)=0 then
string s = sort(sprint(p))
if sort(sprint(p1))=s
and sort(sprint(p2))=s then
if p>=nc then showt() end if
count += 1
if count<=25 then
orm25[count] = sprintf("%d",{p2})
if count=25 then showt() end if
end if
end if
elsif time()>t1 then
progress("%,d\r",{p})
t1 = time()+1
end if
end while
showt()
</syntaxhighlight>
{{out}}
<pre>
|