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>

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>

#include "prime_sieve.hpp"

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

return 0;

 

Contents of prime_sieve.hpp:

#define PRIME_SIEVE_HPP

 

}

 

 

{{out}}

=={{header|D}}==

{{trans|Java}}

import std.array;

import std.conv;

writefln(" %d is %,d", i, v);

}

{{out}}

<pre>First 35 unprimeable numbers:

===The function===

This task uses [http://www.rosettacode.org/wiki/Extensible_prime_generator#The_functions Extensible Prime Generator (F#)]

// Unprimeable numbers. Nigel Galloway: May 4th., 2021

let rec fN i g e l=seq{yield! [0..9]|>Seq.map(fun n->n*g+e+l); if g>1 then let g=g/10 in yield! fN(i+g*(e/g)) g (e%g) i}

let fG(n,g)=fN(n*(g/n)) n (g%n) 0|>Seq.exists(isPrime)

let uP()=let rec fN n g=seq{yield! {n..g-1}|>Seq.map(fun g->(n,g)); yield! fN(g)(g*10)} in fN 1 10|>Seq.filter(fG>>not)|>Seq.map snd

===The Task===

uP()|>Seq.take 35|>Seq.iter(printf "%d "); printfn ""

{{out}}

<pre>

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

</pre>

printfn "600th unprimable number is %d" (uP()|>Seq.item 599)

{{out}}

<pre>

600th unprimable number is 5242

</pre>

[0..9]|>Seq.iter(fun n->printfn "first umprimable number ending in %d is %d" n (uP()|>Seq.find(fun g->n=g%10)))

{{out}}

<pre>

===Optimized for optional part of task===

The above general implementation can complete all of the task but takes over 1min for the optional part. The following completes the optional part in 3secs.

let uPx x=let rec fN n g=seq{yield! {n+x..10..g-1}|>Seq.map(fun g->(max 1 n,g)); yield! fN(g)(g*10)} in fN 0 10|>Seq.filter(fG>>not)|>Seq.map snd

[0..9]|>Seq.iter(fun n->printfn "first umprimable number ending in %d is %d" n (uPx n|>Seq.head))

{{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 unprimeable number ending with" print

{{out}}

<pre>

</pre>

=={{header|FreeBASIC}}==

Function isprime(n As Ulongint) As boolean

If (n=2) Or (n=3) Then Return 1

Next z

sleep

<pre>

First 35

=={{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>

=={{header|J}}==

Reshaping data is a strength of j.

NB. replace concatenates at various ranks and in boxes to avoid fill

NB. the curtailed prefixes (}:\) with all of 0..9 (i.10) with the beheaded suffixes (}.\.)

 

assert 0 1 -: unprimable 193 200

<pre>

NB. test 2e6 integers for unprimability

 

=={{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)

=={{header|Kotlin}}==

{{trans|Java}}

private val primes = BooleanArray(MAX)

 

}

}

{{out}}

<pre>First 35 unprimeable numbers:

 

=={{header|Lua}}==

local function T(t) return setmetatable(t, {__index=table}) end

table.filter = function(t,f) local s=T{} for _,v in ipairs(t) do if f(v) then s[#s+1]=v end end return s end

for i = 0, 9 do

print(" " .. i .. " is: " .. commafy(lowests[i]))

{{out}}

<pre>The first 35 unprimable numbers are:

8 is: 208

9 is: 212,159</pre>

 

=={{header|Nim}}==

 

const N = 10_000_000

while not n.isUmprimeable:

inc n, 10

 

{{out}}

{{trans|Go}} {{works with|Free Pascal}}{{works with|Delphi}}

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}

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

{$IFNDEF UNIX}readln;{$ENDIF}

{{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:

=={{header|Racket}}==

 

 

(require math/number-theory)

(check-equal? (primeable? 10) 11)

(check-true (unprimeable? 200))

 

{{out}}

=={{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*/

Lm= length(j) /*obtain the length-1 of the number J. */

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:}}

 

</pre>

 

=={{header|Rust}}==

{{trans|C++}}

mod bit_array;

mod prime_sieve;

println!("Least unprimeable number ending in {}: {}", i, lowest[i]);

}

 

use crate::bit_array;

 

!self.composite.get(n / 2 - 1)

}

 

pub struct BitArray {

array: Vec<u32>,

}

}

 

{{out}}

 

=={{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>

=={{header|Swift}}==

{{trans|Rust}}

 

class BitArray {

let str = NumberFormatter.localizedString(from: number, number: .decimal)

print("Least unprimeable number ending in \(i): \(str)")

 

{{out}}

{{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>