Unprimeable numbers: Difference between revisions

{{trans|Python}}

 

V is_prime = [0B] * 2 [+] [1B] * (limit - 1)

L(n) 0 .< Int(limit ^ 0.5 + 1.5)

 

L(v) first

 

{{out}}

If running this with Algol 68G under Windows (and possibly other platforms) you will need to increase the heap size by specifying e.g. <code>-heap 256M</code> on the command line.

{{libheader|ALGOL 68-primes}}

# construct a sieve of primes up to max prime #

PR read "primes.incl.a68" PR

)

OD

{{out}}

<pre>

First unprimeable number ending in 9: 212,159

</pre>

 

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

=={{header|JavaScript}}==

Auxiliary function:

Number.prototype.isPrime = function() {

let i = 2, num = this;

return true;

}

 

Core function:

function isUnprimable(num) {

if (num < 100 || num.isPrime()) return false;

return true;

}

 

Main function for output:

let unprimeables = [],

endings = new Array(10).fill('-'),

}

console.timeEnd('II');

 

{{out}}

 

'''Preliminaries'''

 

def lpad($len): tostring | ($len - length) as $l | (" " * $l)[:$l] + .;

'''Unprimeables'''

def variants:

digits

 

def unprimeables:

 

'''The Tasks'''

"First 35 unprimeables: ",

[limit(35; range(0;infinite) | select(is_unprimeable))],

;

 

{{out}}

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

 

=={{header|Mathematica}} / {{header|Wolfram Language}}==

Unprimeable[in_Integer] := Module[{id, new, pos},

id = IntegerDigits[in];

 

lastdigit = IntegerDigits /* Last;

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

 

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

<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>

<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"The first 35 unprimeable numbers are:\n"</span><span style="color: #0000FF;">)</span>

<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>

<span style="color: #0000FF;">?</span><span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">)</span>

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

 

With the addition of the computation of squared primes, &nbsp; the program now is about '''4''' times faster.

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

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

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

#= #+1; if #<=lim then @.#=j; !.j=1 /*bump prime count; assign prime to @. */

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