Twin primes: Difference between revisions
Line 463: | Line 463: | ||
Under 10,000,000 there are 58,980 pairs of twin primes. |
Under 10,000,000 there are 58,980 pairs of twin primes. |
||
Under 100,000,000 there are 440,312 pairs of twin primes. |
Under 100,000,000 there are 440,312 pairs of twin primes. |
||
</pre> |
|||
==Tuple Generalization== |
|||
<p>We can generalize pairs to reflect any tuple of integer diffences between the first prime |
|||
and the successive primes: see http://www.rosettacode.org/wiki/Successive_prime_differences. |
|||
</p><p> |
|||
If we ignore the first difference from the index prime with itself (always 0), we can express a |
|||
prime pair as a diffence tuple of (2,), and a prime quadruplet such as [11, 3, 17, 19] as the |
|||
tuple starting with 11 of type (2, 6, 8). |
|||
</p> |
|||
<lang julia>using Primes |
|||
tuplefitsat(k, tup, arr) = all(i -> arr[k + i] - arr[k] == tup[i], 1:length(tup)) |
|||
function countprimetuples(tup, n) |
|||
arr = [i for i in 2:n if isprime(i)] |
|||
return count(k -> tuplefitsat(k, tup, arr), 1:length(arr) - length(tup)) |
|||
end |
|||
println("Count of prime pairs from 1 to 1 million: ", countprimetuples((2,), 1000000)) |
|||
println("Count of a form of prime quads from 1 to 1 million: ", |
|||
countprimetuples((2, 6, 8), 1000000)) |
|||
println("Count of a form of prime octets from 1 to 1 million: ", |
|||
countprimetuples((2, 6, 12, 14, 20, 24, 26), 1000000)) |
|||
</lang>{{out}} |
|||
<pre> |
|||
Count of prime pairs from 1 to 1 million: 8169 |
|||
Count of a form of prime quads from 1 to 1 million: 166 |
|||
Count of a form of prime octets from 1 to 1 million: 3 |
|||
</pre> |
</pre> |
||
Revision as of 03:17, 28 July 2020
Twin primes are pairs of natural numbers (P1 and P2) that satisfy the following:
- P1 and P2 are primes
- P1 + 2 = P2
- Task
Write a program that displays the number of pairs of twin primes that can be found under a user-specified number
(P1 < user-specified number & P2 < user-specified number).
- Extension
-
- Find all twin prime pairs under 100000, 10000000 and 1000000000.
- What is the time complexity of the program? Are there ways to reduce computation time?
- Examples
> Search Size: 100 > 8 twin prime pairs.
> Search Size: 1000 > 35 twin prime pairs.
- Also see
- The OEIS entry: A001097 Twin primes.
- The OEIS entry: A167874 The number of distinct primes < 10^n which are members of twin-prime pairs.
- The OEIS entry: A077800 List of twin primes {p, p+2}, with repetition.
- The OEIS entry: A007508 Number of twin prime pairs below 10^n.
ALGOL 68
Simplifies array bound checking by using the equivalent definition of twin primes: p and p - 2. <lang algol68>BEGIN
# count twin primes (where p and p - 2 are prime) # PR heap=128M PR # set heap memory size for Algol 68G # # sieve of Eratosthenes: sets s[i] to TRUE if i is a prime, FALSE otherwise # PROC sieve = ( REF[]BOOL s )VOID: BEGIN FOR i TO UPB s DO s[ i ] := TRUE OD; s[ 1 ] := FALSE; FOR i FROM 2 TO ENTIER sqrt( UPB s ) DO IF s[ i ] THEN FOR p FROM i * i BY i TO UPB s DO s[ p ] := FALSE OD FI OD END # sieve # ; # find the maximum number to search for twin primes # INT max; print( ( "Maximum: " ) ); read( ( max, newline ) ); INT max number = max; # construct a sieve of primes up to the maximum number # [ 1 : max number ]BOOL primes; sieve( primes ); # count the twin primes # # note 2 cannot be one of the primes in a twin prime pair, so we start at 3 # INT twin count := 0; FOR p FROM 3 BY 2 TO max number - 1 DO IF primes[ p ] AND primes[ p - 2 ] THEN twin count +:= 1 FI OD; print( ( "twin prime pairs below ", whole( max number, 0 ), ": ", whole( twin count, 0 ), newline ) )
END</lang>
- Output:
Maximum: 10 twin prime pairs below 10: 2
Maximum: 100 twin prime pairs below 100: 8
Maximum: 1000 twin prime pairs below 1000: 35
Maximum: 10000 twin prime pairs below 10000: 205
Maximum: 100000 twin prime pairs below 100000: 1224
Maximum: 1000000 twin prime pairs below 1000000: 8169
Maximum: 10000000 twin prime pairs below 10000000: 58980
C++
The primesieve library includes the functionality required for this task. RC already has plenty of C++ examples showing how to generate prime numbers from scratch. (The module Math::Primesieve, which is used by the Raku example on this page, is implemented on top of this library.) <lang cpp>#include <cstdint>
- include <iostream>
- include <string>
- include <primesieve.hpp>
void print_twin_prime_count(long long limit) {
std::cout << "Number of twin prime pairs less than " << limit << " is " << (limit > 0 ? primesieve::count_twins(0, limit - 1) : 0) << '\n';
}
int main(int argc, char** argv) {
std::cout.imbue(std::locale("")); if (argc > 1) { // print number of twin prime pairs less than limits specified // on the command line for (int i = 1; i < argc; ++i) { try { print_twin_prime_count(std::stoll(argv[i])); } catch (const std::exception& ex) { std::cerr << "Cannot parse limit from '" << argv[i] << "'\n"; } } } else { // if no limit was specified then show the number of twin prime // pairs less than powers of 10 up to 100 billion uint64_t limit = 10; for (int power = 1; power < 12; ++power, limit *= 10) print_twin_prime_count(limit); } return 0;
}</lang>
- Output:
Number of twin prime pairs less than 10 is 2 Number of twin prime pairs less than 100 is 8 Number of twin prime pairs less than 1,000 is 35 Number of twin prime pairs less than 10,000 is 205 Number of twin prime pairs less than 100,000 is 1,224 Number of twin prime pairs less than 1,000,000 is 8,169 Number of twin prime pairs less than 10,000,000 is 58,980 Number of twin prime pairs less than 100,000,000 is 440,312 Number of twin prime pairs less than 1,000,000,000 is 3,424,506 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
Delphi
<lang Delphi> program Primes;
{$APPTYPE CONSOLE}
{$R *.res}
uses
System.SysUtils;
function IsPrime(a: UInt64): Boolean; var
d: UInt64;
begin
if (a < 2) then exit(False);
if (a mod 2) = 0 then exit(a = 2);
if (a mod 3) = 0 then exit(a = 3);
d := 5;
while (d * d <= a) do begin if (a mod d = 0) then Exit(false); inc(d, 2);
if (a mod d = 0) then Exit(false); inc(d, 4); end;
Result := True;
end;
function Sieve(limit: UInt64): TArray<Boolean>;
var
p, p2, i: UInt64;
begin
inc(limit); SetLength(Result, limit); FillChar(Result[2], sizeof(Boolean) * limit - 2, 0); // all false except 1,2 FillChar(Result[0], sizeof(Boolean) * 2, 1); // 1,2 are true
p := 3; while true do begin p2 := p * p; if p2 >= limit then break;
i := p2; while i < limit do begin Result[i] := true; inc(i, 2 * p); end;
while true do begin inc(p, 2); if not Result[p] then Break; end; end;
end;
function Commatize(const n: UInt64): string; var
str: string; digits: Integer; i: Integer;
begin
Result := ; str := n.ToString; digits := str.Length;
for i := 1 to digits do begin if ((i > 1) and (((i - 1) mod 3) = (digits mod 3))) then Result := Result + ','; Result := Result + str[i]; end;
end;
var
limit, start, twins: UInt64; c: TArray<Boolean>; i, j: UInt64;
begin
c := Sieve(Trunc(1e9 - 1)); limit := 10; start := 3; twins := 0; for i := 1 to 9 do begin j := start; while j < limit do begin if (not c[j]) and (not c[j - 2]) then inc(twins); inc(j, 2); end; Writeln(Format('Under %14s there are %10s pairs of twin primes.', [commatize (limit), commatize(twins)]));
start := limit + 1; limit := 10 * limit; end;
readln;
end.
</lang>
- Output:
Under 10 there are 2 pairs of twin primes. Under 100 there are 8 pairs of twin primes. Under 1,000 there are 35 pairs of twin primes. Under 10,000 there are 205 pairs of twin primes. Under 100,000 there are 1,224 pairs of twin primes. Under 1,000,000 there are 8,169 pairs of twin primes. Under 10,000,000 there are 58,980 pairs of twin primes. Under 100,000,000 there are 440,312 pairs of twin primes. Under 1,000,000,000 there are 3,424,506 pairs of twin primes.
Factor
<lang factor>USING: io kernel math math.parser math.primes.erato math.ranges sequences tools.memory.private ;
- twin-pair-count ( n -- count )
[ 5 swap 2 <range> ] [ sieve ] bi [ over 2 - over [ marked-prime? ] 2bi@ and ] curry count ;
"Search size: " write flush readln string>number twin-pair-count commas write " twin prime pairs." print</lang>
- Output:
Search size: 100,000 1,224 twin prime pairs.
Search size: 10,000,000 58,980 twin prime pairs.
Search size: 1,000,000,000 3,424,506 twin prime pairs.
Go
<lang go>package main
import "fmt"
func sieve(limit uint64) []bool {
limit++ // True denotes composite, false denotes prime. c := make([]bool, limit) // all false by default c[0] = true c[1] = true // no need to bother with even numbers over 2 for this task p := uint64(3) // Start from 3. for { p2 := p * p if p2 >= limit { break } for i := p2; i < limit; i += 2 * p { c[i] = true } for { p += 2 if !c[p] { break } } } return c
}
func commatize(n int) string {
s := fmt.Sprintf("%d", n) if n < 0 { s = s[1:] } le := len(s) for i := le - 3; i >= 1; i -= 3 { s = s[0:i] + "," + s[i:] } if n >= 0 { return s } return "-" + s
}
func main() {
c := sieve(1e10 - 1) limit := 10 start := 3 twins := 0 for i := 1; i < 11; i++ { for i := start; i < limit; i += 2 { if !c[i] && !c[i-2] { twins++ } } fmt.Printf("Under %14s there are %10s pairs of twin primes.\n", commatize(limit), commatize(twins)) start = limit + 1 limit *= 10 }
}</lang>
- Output:
Under 10 there are 2 pairs of twin primes. Under 100 there are 8 pairs of twin primes. Under 1,000 there are 35 pairs of twin primes. Under 10,000 there are 205 pairs of twin primes. Under 100,000 there are 1,224 pairs of twin primes. Under 1,000,000 there are 8,169 pairs of twin primes. Under 10,000,000 there are 58,980 pairs of twin primes. Under 100,000,000 there are 440,312 pairs of twin primes. Under 1,000,000,000 there are 3,424,506 pairs of twin primes. Under 10,000,000,000 there are 27,412,679 pairs of twin primes.
Java
BigInteger Implementation: <lang Java> import java.math.BigInteger; import java.util.Scanner;
public class twinPrimes {
public static void main(String[] args) { Scanner input = new Scanner(System.in); System.out.println("Search Size: "); BigInteger max = input.nextBigInteger(); int counter = 0; for(BigInteger x = new BigInteger("3"); x.compareTo(max) <= 0; x = x.add(BigInteger.ONE)){ BigInteger sqrtNum = x.sqrt().add(BigInteger.ONE); if(x.add(BigInteger.TWO).compareTo(max) <= 0) { counter += findPrime(x.add(BigInteger.TWO), x.add(BigInteger.TWO).sqrt().add(BigInteger.ONE)) && findPrime(x, sqrtNum) ? 1 : 0; } } System.out.println(counter + " twin prime pairs."); } public static boolean findPrime(BigInteger x, BigInteger sqrtNum){ for(BigInteger divisor = BigInteger.TWO; divisor.compareTo(sqrtNum) <= 0; divisor = divisor.add(BigInteger.ONE)){ if(x.remainder(divisor).compareTo(BigInteger.ZERO) == 0){ return false; } } return true; }
} </lang>
- Output:
> Search Size: > 100 > 8 twin prime pairs.
> Search Size: > 1000 > 35 twin prime pairs.
Julia
<lang julia>using Formatting, Primes
function counttwinprimepairsbetween(n1, n2)
npairs, t = 0, nextprime(n1) while t < n2 p = nextprime(t + 1) if p - t == 2 npairs += 1 end t = p end return npairs
end
for t2 in (10).^collect(2:8)
paircount = counttwinprimepairsbetween(1, t2) println("Under", lpad(format(t2, commas=true), 12), " there are", lpad(format(paircount, commas=true), 8), " pairs of twin primes.")
end
</lang>
- Output:
Under 100 there are 8 pairs of twin primes. Under 1,000 there are 35 pairs of twin primes. Under 10,000 there are 205 pairs of twin primes. Under 100,000 there are 1,224 pairs of twin primes. Under 1,000,000 there are 8,169 pairs of twin primes. Under 10,000,000 there are 58,980 pairs of twin primes. Under 100,000,000 there are 440,312 pairs of twin primes.
Perl
<lang perl>use strict; use warnings;
use Primesieve;
sub comma { reverse ((reverse shift) =~ s/(.{3})/$1,/gr) =~ s/^,//r }
printf "Twin prime pairs less than %14s: %s\n", comma(10**$_), comma count_twins(1, 10**$_) for 1..10;</lang>
- Output:
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
Phix
Added both parameter to reflect the recent task specification changes, as shown for a limit of 6 you can count {3,5} and {5,7} as one pair (the default, matching task description) or two. Obviously delete the "6 --" if you actually want a prompt.
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. <lang Phix>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</lang>
- Output:
Twin prime pairs less than 6: 1 Twin prime pairs less than 6: 2 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
Raku
<lang perl6>use Lingua::EN::Numbers;
use Math::Primesieve;
my $p = Math::Primesieve.new;
printf "Twin prime pairs less than %14s: %s\n", comma(10**$_), comma $p.count(10**$_, :twins) for 1 .. 10;</lang>
- Output:
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
REXX
The genP function could be optimized for higher specifications of the limit(s). <lang rexx>/*REXX pgm counts the number of twin prime pairs under a specified number N (or a list).*/ parse arg $ . /*get optional number of primes to find*/ if $= | $="," then $= 10 100 1000 10000 100000 1000000 10000000 /*No $? Use default.*/ w= length( commas( word($, words($) ) ) ) /*get length of the last number in list*/ @found= ' twin prime pairs found under ' /*literal used in the showing of output*/
do i=1 for words($); x= word($, i) /*process each N─limit in the $ list.*/ say right( commas(genP(x)), 20) @found right(commas(x), max(length(x), w) ) end /*i*/
exit 0 /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ commas: parse arg _; do ?=length(_)-3 to 1 by -3; _=insert(',', _, ?); end; return _ /*──────────────────────────────────────────────────────────────────────────────────────*/ genP: parse arg y; @.1=2; @.2=3; @.3=5; @.4=7; @.5=11; @.6=13; #= 5; tp= 2
do j=13 by 2 while j<y /*continue on with the next odd prime. */ parse var j -1 _ /*obtain the last digit of the J var.*/ if _ ==5 then iterate /*is this integer a multiple of five? */ if j // 3 ==0 then iterate /* " " " " " " three? */ if j // 7 ==0 then iterate /* " " " " " " seven? */ if j //11 ==0 then iterate /* " " " " " " eleven?*/ /* [↓] divide by the primes. ___ */ do k=6 to # while k*k<=j /*divide J by other primes ≤ √ J */ if j//@.k == 0 then iterate j /*÷ by prev. prime? ¬prime ___ */ end /*k*/ /* [↑] only divide up to √ J */ prev= @.#; #= # + 1; @.#= j /*save prev. P; bump # primes; assign P*/ if j-2==prev then tp= tp + 1 /*This & previous prime twins? Bump TP.*/ end /*j*/ return tp</lang>
- output when using the default inputs:
2 twin prime pairs found under 10 8 twin prime pairs found under 100 35 twin prime pairs found under 1,000 205 twin prime pairs found under 10,000 1,224 twin prime pairs found under 100,000 8,169 twin prime pairs found under 1,000,000 58,980 twin prime pairs found under 10,000,000
Rust
Limits can be specified on the command line, otherwise the twin prime counts for powers of ten from 1 to 10 are shown. <lang rust>// [dependencies] // primal = "0.3" // num-format = "0.4"
use num_format::{Locale, ToFormattedString};
fn twin_prime_count_for_powers_of_ten(max_power: u32) {
let mut count = 0; let mut previous = 0; let mut power = 1; let mut limit = 10; for prime in primal::Primes::all() { if prime > limit { println!( "Number of twin prime pairs less than {} is {}", limit.to_formatted_string(&Locale::en), count.to_formatted_string(&Locale::en) ); limit *= 10; power += 1; if power > max_power { break; } } if previous > 0 && prime == previous + 2 { count += 1; } previous = prime; }
}
fn twin_prime_count(limit: usize) {
let mut count = 0; let mut previous = 0; for prime in primal::Primes::all().take_while(|x| *x < limit) { if previous > 0 && prime == previous + 2 { count += 1; } previous = prime; } println!( "Number of twin prime pairs less than {} is {}", limit.to_formatted_string(&Locale::en), count.to_formatted_string(&Locale::en) );
}
fn main() {
let args: Vec<String> = std::env::args().collect(); if args.len() > 1 { for i in 1..args.len() { if let Ok(limit) = args[i].parse::<usize>() { twin_prime_count(limit); } else { eprintln!("Cannot parse limit from string {}", args[i]); } } } else { twin_prime_count_for_powers_of_ten(10); }
}</lang>
- Output:
Number of twin prime pairs less than 10 is 2 Number of twin prime pairs less than 100 is 8 Number of twin prime pairs less than 1,000 is 35 Number of twin prime pairs less than 10,000 is 205 Number of twin prime pairs less than 100,000 is 1,224 Number of twin prime pairs less than 1,000,000 is 8,169 Number of twin prime pairs less than 10,000,000 is 58,980 Number of twin prime pairs less than 100,000,000 is 440,312 Number of twin prime pairs less than 1,000,000,000 is 3,424,506 Number of twin prime pairs less than 10,000,000,000 is 27,412,679
Wren
<lang ecmascript>import "/math" for Int import "/fmt" for Fmt
var c = Int.primeSieve(1e8-1, false) var limit = 10 var start = 3 var twins = 0 for (i in 1..8) {
var j = start while (j < limit) { if (!c[j] && !c[j-2]) twins = twins + 1 j = j + 2 } Fmt.print("Under $,11d there are $,7d pairs of twin primes.", limit, twins) start = limit + 1 limit = limit * 10
}</lang>
- Output:
Under 100 there are 8 pairs of twin primes. Under 1,000 there are 35 pairs of twin primes. Under 10,000 there are 205 pairs of twin primes. Under 100,000 there are 1,224 pairs of twin primes. Under 1,000,000 there are 8,169 pairs of twin primes. Under 10,000,000 there are 58,980 pairs of twin primes. Under 100,000,000 there are 440,312 pairs of twin primes.