Twin primes: Difference between revisions
m
→{{header|Wren}}: Minor tidy
m (New post which completes the extended task, in addition to an existing post which completes only the standard task.) |
m (→{{header|Wren}}: Minor tidy) |
||
(8 intermediate revisions by 5 users not shown) | |||
Line 347:
Number of twin prime pairs less than 10,000,000,000 is 27,412,679
Number of twin prime pairs less than 100,000,000,000 is 224,376,048
</pre>
===Without external libraries===
<syntaxhighlight lang="c++">
#include <bitset>
#include <cstdint>
#include <iomanip>
#include <iostream>
#include <vector>
const uint32_t limit = 1'000'000'000;
std::bitset<limit + 1> primes;
void sieve_primes(uint32_t limit) {
primes.set();
primes.reset(0); primes.reset(1);
for ( uint32_t p = 2; p * p <= limit; ++p ) {
if ( primes.test(p) ) {
for ( uint32_t i = p * p; i <= limit; i += p ) {
primes.reset(i);
}
}
}
}
int main() {
sieve_primes(limit);
uint32_t target = 10;
uint32_t count = 0;
bool last = false;
bool first = true;
for ( uint32_t index = 5; index <= limit; index += 2 ) {
last = first;
first = primes[index];
if ( last && first ) {
count += 1;
}
if ( index + 1 == target ) {
std::cout << std::setw(8) << count << " twin primes below " << index + 1 << std::endl;
target *= 10;
}
}
}
</syntaxhighlight>
{{ out }}
<pre>
2 twin primes below 10
8 twin primes below 100
35 twin primes below 1000
205 twin primes below 10000
1224 twin primes below 100000
8169 twin primes below 1000000
58980 twin primes below 10000000
440312 twin primes below 100000000
3424506 twin primes below 1000000000
</pre>
Line 637 ⟶ 695:
Under 1,000,000,000 there are 3,424,506 pairs of twin primes.
</pre>
=={{header|EasyLang}}==
{{trans|AWK}}
<syntaxhighlight lang=easylang>
fastfunc isprim num .
if num mod 2 = 0 and num > 2
return 0
.
i = 3
while i <= sqrt num
if num mod i = 0
return 0
.
i += 2
.
return 1
.
func count limit .
p2 = 1
p3 = 1
for i = 5 to limit
p3 = p2
p2 = p1
p1 = isprim i
if p3 = 1 and p1 = 1
cnt += 1
.
.
return cnt
.
n = 1
for i = 1 to 6
n *= 10
print "twin prime pairs < " & n & " : " & count n
.
</syntaxhighlight>
=={{header|F Sharp|F#}}==
Line 986 ⟶ 1,080:
=={{header|J}}==
<syntaxhighlight lang="j">tp=:
NB. i.&.(p:inv) generate a list of primes below the given limit
NB.
NB. _2 +/@:= compare these differences to -2, and
NB. sum up the resulting boolean list (get the number of twin pairs)</syntaxhighlight>
{{out}}
<pre> tp
2 8 35 205 1224 8169 58980
NB. test larger limits, and get their time/space usage
tp
440312
timespacex 'tp
0.657576 2.01377e8
tp 1e9
3424506
timespacex 'tp 1e9'
8.59713 1.61071e9
</pre>
=={{header|jq}}==
Line 1,281 ⟶ 1,372:
The time complexity here is all about building a table of primes. It turns out that using the builtin get_prime() is actually faster
than using an explicit sieve (as per Delphi/Go/Wren) due to retaining all the intermediate 0s, not that I particularly expect this to win any performance trophies.
<!--
<syntaxhighlight lang="phix">
with javascript_semantics
atom t0 = time()
function twin_primes(integer maxp, bool both=true)
integer n = 0, -- result
pn = 2, -- next prime index
p, -- a prime, <= maxp
prev_p = 2
while true do
p = get_prime(pn)
if both and p>=maxp then exit end if
n += (prev_p = p-2)
if (not both) and p>=maxp then exit end if
prev_p = p
pn += 1
end while
return n
end function
integer mp = 6 -- prompt_number("Enter limit:")
printf(1,"Twin prime pairs less than %,d: %,d\n",{mp,twin_primes(mp)})
printf(1,"Twin prime pairs less than %,d: %,d\n",{mp,twin_primes(mp,false)})
for p=1 to 9 do
integer p10 = power(10,p)
printf(1,"Twin prime pairs less than %,d: %,d\n",{p10,twin_primes(p10)})
end for
?elapsed(time()-t0)
</syntaxhighlight>
{{out}}
<pre>
Line 1,323 ⟶ 1,415:
"16.2s"
</pre>
=== using primesieve ===
Windows 64-bit only, unless you can find/make a suitable dll/so.<br>
Note that unlike the above this version of twin_primes() carries on from where it left off.
<syntaxhighlight lang="phix">
requires(WINDOWS)
requires(64,true)
include builtins/primesieve.e
atom t0 = time()
integer n = 0, p = 2, prev_p = 2
function twin_primes(integer maxp, bool both=true)
while true do
if both and p>=maxp then exit end if
n += (prev_p = p-2)
if (not both) and p>=maxp then exit end if
prev_p = p
p = primesieve_next_prime()
end while
return n
end function
for i=1 to 11 do
integer p10 = power(10,i)
printf(1,"Twin prime pairs less than %,d: %,d\n",{p10,twin_primes(p10)})
end for
?elapsed(time()-t0)
</syntaxhighlight>
{{out}}
Same as above, which it completes in 7.2s (and 1e10 in 1 min 6s), less the 6's and plus two more lines:
<pre>
Twin prime pairs less than 10: 2
Twin prime pairs less than 100: 8
Twin prime pairs less than 1,000: 35
Twin prime pairs less than 10,000: 205
Twin prime pairs less than 100,000: 1,224
Twin prime pairs less than 1,000,000: 8,169
Twin prime pairs less than 10,000,000: 58,980
Twin prime pairs less than 100,000,000: 440,312
Twin prime pairs less than 1,000,000,000: 3,424,506
Twin prime pairs less than 10,000,000,000: 27,412,679
Twin prime pairs less than 100,000,000,000: 224,376,048
"10 minutes and 25s"
</pre>
=={{header|PureBasic}}==
Line 1,470 ⟶ 1,602:
my $p = Math::Primesieve.new;
printf "Twin prime pairs less than %
say (now - INIT now).round(.01) ~ ' seconds';</syntaxhighlight>
{{out}}
<pre>Twin prime pairs less than 10: 2
Twin prime pairs less than 100: 8
Twin prime pairs less than 1,000: 35
Twin prime pairs less than 10,000: 205
Twin prime pairs less than 100,000: 1,224
Twin prime pairs less than 1,000,000: 8,169
Twin prime pairs less than 10,000,000: 58,980
Twin prime pairs less than 100,000,000: 440,312
Twin prime pairs less than 1,000,000,000: 3,424,506
Twin prime pairs less than 10,000,000,000: 27,412,679
Twin prime pairs less than 100,000,000,000: 224,376,048
Twin prime pairs less than 1,000,000,000,000: 1,870,585,220
6.89 seconds</pre>
=={{header|REXX}}==
Line 1,819 ⟶ 1,955:
{{libheader|Wren-math}}
{{libheader|Wren-fmt}}
<syntaxhighlight lang="
import "./fmt" for Fmt
var c = Int.primeSieve(1e8-1, false)
|