Unprimeable numbers: Difference between revisions

:*   from the Adam Spencer book   (page 200):   ''Adam Spencer's World of Numbers''       (Xoum Publishing)

<br><br>

 

=={{header|C}}==

{{trans|C++}}

#include <locale.h>

#include <stdbool.h>

 

bool sieve_create(sieve* s, uint32_t limit) {

if (!bit_array_create(&s->not_prime, limit/2))

return false;

printf("\n600th unprimeable number: %'u\n", n);

uint32_t last_digit = n % 10;

lowest[last_digit] = n;

++found;

printf("Least unprimeable number ending in %u: %'u\n" , i, lowest[i]);

return 0;

 

{{out}}

 

=={{header|C++}}==

#include <cstdint>

 

typedef uint32_t integer;

 

// return number of decimal digits

int digits = 0;

for (; n > 0; ++digits)

 

// return the number with one digit replaced

integer p = 1;

integer changed = 0;

 

// returns true if n unprimeable

if (sieve.is_prime(n))

return false;

int d = count_digits(n);

integer m = change_digit(n, i, j);

if (m != n && sieve.is_prime(m))

}

 

const integer limit = 10000000;

 

// print numbers with commas

std::cout.imbue(std::locale(""));

 

std::cout << "First 35 unprimeable numbers:\n";

integer n = 100;

integer lowest[10] = { 0 };

if (count != 0)

std::cout << ", ";

std::cout << "\n600th unprimeable number: " << n << '\n';

int last_digit = n % 10;

lowest[last_digit] = n;

++found;

std::cout << "Least unprimeable number ending in " << i << ": " << lowest[i] << '\n';

return 0;

 

 

#include <algorithm>

#include <vector>

 

public:

bool is_prime(size_t) const;

private:

};

 

for (size_t p = 3; p * p <= limit; p += 2) {

size_t inc = 2 * p;

for (size_t q = p * p; q <= limit; q += inc)

}

}

}

 

 

{{out}}

</pre>

 

=={{header|Factor}}==

{{works with|Factor|0.99 2019-10-06}}

lists.lazy.examples math math.functions math.primes math.ranges

math.text.utils prettyprint sequences tools.memory.private ;

 

"The first 35 unprimeable numbers:" print bl bl

 

"The 600th unprimeable number:" print bl bl

 

"The first unprimeable number ending with" print

{{out}}

<pre>

8: 208

9: 212,159

</pre>

 

=={{header|Go}}==

Simple brute force (no sieves, memoization or bigint.ProbablyPrime) as there is not much need for speed here.

 

import (

fmt.Printf(" %d is: %9s\n", i, commatize(firstNum[i]))

}

 

{{out}}

</pre>

=={{header|Haskell}}==

import Data.Numbers.Primes (isPrime)

import Data.List (find, intercalate)

lowest n = do

x <- find (\x -> x `mod` 10 == n) unPrimeable

{{out}}

<pre>

Lowest unprimeable number ending with 8: 208

Lowest unprimeable number ending with 9: 212,159

</pre>

 

=={{header|Java}}==

public class UnprimeableNumbers {

 

 

}

 

{{out}}

9 is 212,159

</pre>

 

=={{header|Julia}}==

 

function isunprimeable(n)

println(" $dig ", lpad(format(n, commas=true), 9))

end

<pre>

First 35 unprimeables: (200 204 206 208 320 322 324 325 326 328 510 512 514 515 516 518 530 532 534 535 536 538 620 622 624 625 626 628 840 842 844 845 846 848 890)

9 212,159

</pre>

 

=={{header|Pascal}}==

Small improvement.When the check of value ending in "0" is not unprimable than I can jump over by 10, since the check already has checked those numbers ending in "1".."9".But in case of unprimable I am using a reduced version of the check<BR>Results in runtime reduced from 1.8 secs downto 0.667 now to 0.46

{$IFDEF FPC}{$Mode Delphi}{$ELSE}{$APPTYPE CONSOLE}{$ENDIF}

const

base = 10;

type

TNumVal = array[0..base-1] of NativeUint;

MaxIdx : NativeUint;

end;

var //global

PotBase,

TotalCnt,

EndDgtCnt :NativeUint;

procedure Init;

var

EndDgtCnt := 0;

end;

Procedure ConvertNum(n: NativeUint;var NConv:TConvNum);

//extract digit position replace by "0" to get NumRest

end;

end;

procedure CheckOutPut(n: NativeUint);

Begin

end;

end;

function isPrime(n : NativeUint):boolean;inline;

var

if n mod p = 0 then

Exit;

if n mod p = 0 then

Exit;

end;

result := true;

end;

procedure InsertFound(LowDgt,n:NativeUInt);

Begin

end;

end;

function CheckUnprimable(n:NativeInt):boolean;

var

EXIT;

dgt := LowDgt;

result := true;

i := MaxIdx;

end;

end;

result := false;

For i := MaxIdx downto 1 do

end;

end;

function CheckUnprimableReduced(n:NativeInt):boolean;

//lowest digit already tested before

end;

end;

result := false;

For i := i downto 1 do

end;

end;

var

n,i : NativeUint;

writeln;

writeln('There are ',TotalCnt,' unprimable numbers upto ',n);

{{out}}

<pre style="font-size:84%">

Base 18= 2*3*3 :lowest digit 7 found first 10,921,015,789<BR>

bases that are prime find their different digits quite early.

{$IFDEF FPC}

{$Mode Delphi}

writeln('There are ',TotalCnt,' unprimable numbers upto ',n);

setlength(Primes,0);

{{out}}

<pre style="height:35ex">

{{trans|Raku}}

{{libheader|ntheory}}

use warnings;

use feature 'say';

while ($x += 10) { last if is_unprimeable($x) }

say "First unprimeable that ends with $_: " . sprintf "%9s", comma $x;

{{out}}

<pre>First 35 unprimeables:

=={{header|Phix}}==

{{trans|Go}}

{{out}}

<pre>

=={{header|Pike}}==

Not the fastest way of doing this, but using string manipulation seemed like the obvious Pike way to do it.

bool is_unprimeable(int i)

{

write(" %s is: %9d\n", e, first_enders[e]);

}

Output:

<pre>

 

=={{header|Python}}==

 

def primes(_cache=[2, 3]):

 

for i,v in enumerate(first):

{{out}}

<pre>First 35:

9 ending: 212159

</pre>

 

=={{header|Raku}}==

(formerly Perl 6)

use Lingua::EN::Numbers;

 

for ^chrs -> \place {

my \pow = 10**(chrs - place - 1);

^10 .map: -> \dgt {

next if this == dgt;

}

}

print "First unprimeable that ends with {n}: " ~

sprintf "%9s\n", comma (n, *+10 … *).race.first: { .&is-unprimeable }

{{out}}

<pre>First 35 unprimeables:

=={{header|REXX}}==

Some effort was put into the optimization of the generation of primes &nbsp; (the &nbsp; '''genP''' &nbsp; subroutine).

parse arg n x hp . /*obtain optional arguments from the CL*/

if n=='' | n=="," then n= 35 /*Not specified? Then use the default.*/

if x=='' | x=="," then x= 600 /* " " " " " " */

if hp=='' | hp=="," then hp= 10000000 /* " " " " " " */

call genP hp /*generate primes up to & including HP.*/

$$=; $.=. /*a list " " " " " */

do j=100; if !.j then iterate /*Prime? Unprimeable must be composite*/

/* [↑] examine the "end" digit of J. */

do e_=1 for eds; new= meat || ed.e_ /*obtain a different number (than J).*/

if !.new then iterate j /*This new number a prime? " " */

end /*f_*/ /* [↑] examine the front digit of J. */

meat= left(j, a_ - 1) /*use a number of left─most dec. digits*/

rest= substr(j, a_ + 1) /* " " " " right─most " " */

end /*n_*/

end /*a_*/

parse var j '' -1 _ /*obtain the right─most dec digit of J.*/

if $._==. then $._= j /*the 1st unprimeable # that ends in _.*/

th:procedure;parse arg x;return x||word('th st nd rd',1+(x//10)*(x//100%10\==1)*(x//10<4))

/*──────────────────────────────────────────────────────────────────────────────────────*/

do lim=100 until lim*lim>=hp /*only keep primes up to the sqrt(hp). */

end /*lim*/ /* [↑] find limit for storing primes. */

end /*k*/ /* [↓] a prime (J) has been found. */

{{out|output|text=&nbsp; when using the default inputs:}}

 

the first unprimeable number that ends in 8 is: 208

the first unprimeable number that ends in 9 is: 212,159

</pre>

 

=={{header|Sidef}}==

var t = 10*floor(n/10)

for k in (t+1 .. t+9 `by` 2) {

say ("First unprimeable that ends with #{d}: ",

1..Inf -> lazy.map {|k| k*10 + d }.grep(is_unprimeable).first)

{{out}}

<pre>

First unprimeable that ends with 8: 208

First unprimeable that ends with 9: 212159

</pre>

 

{{libheader|Wren-fmt}}

{{libheader|Wren-math}}

 

System.print("The first 35 unprimeable numbers are:")

System.print("The first unprimeable number that ends in:")

 

{{out}}

8 is: 208

9 is: 212,159

</pre>

 

{{trans|Sidef}}

{{libheader|GMP}} GNU Multiple Precision Arithmetic Library and fast prime checking

 

fcn isUnprimeable(n){ //--> n (!0) or Void, a filter

n

}

println("The 600th unprimeable number is: %,d".fmt(isUnprimeableW().drop(600).value));

 

{ d:=up%10; if(ups[d]==0){ ups[d]=up; if((s-=1)<=0) break; } }

println("The first unprimeable number that ends in:");

{{out}}

<pre>