Semiprime: Difference between revisions

{{trans|C++}}

 

V a = 2

V b = 0

R b == 2

 

 

{{out}}

=={{header|360 Assembly}}==

{{trans|C}}

SEMIPRIM CSECT

USING SEMIPRIM,R13 base register

XDEC DS CL12 temp

YREGS

{{out}}

<pre>

 

=={{header|Action!}}==

INT a,b

 

FI

OD

{{out}}

[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Semiprime.png Screenshot from Atari 8-bit computer]

This imports the package '''Prime_Numbers''' from [[Prime decomposition#Ada]].

 

procedure Test_Semiprime is

end if;

end loop;

 

It outputs all semiprimes below 100 and all semiprimes between 1675 and 1680:

 

=={{header|ALGOL 68}}==

# n is semi prime if it has exactly two prime factors #

PROC is semiprime = ( INT n )BOOL:

OD;

print( ( newline ) )

{{out}}

<pre>

=={{header|Arturo}}==

 

2 = size factors.prime x

]

 

 

{{out}}

=={{header|AutoHotkey}}==

{{works with|AutoHotkey_L}}

k := 1

loop, 100

}

;=================================================================================================================================================

{{output}}

<Pre>

 

=={{header|AWK}}==

# syntax: GAWK -f SEMIPRIME.AWK

BEGIN {

return(nf == 2)

}

{{out}}

<pre>

==={{header|ASIC}}===

{{trans|Tiny BASIC}}

REM Semiprime

PRINT "Enter an integer ";

ENDIF

END

{{out}}

<pre>

 

==={{header|BASIC256}}===

a = 2

c = 0

print i, semiprime$(i)

next i

 

==={{header|FreeBASIC}}===

dim as uinteger a = 2, c = 0

while c < 3 andalso n > 1

for i as uinteger = 0 to 64

print i, semiprime(i)

 

==={{header|GW-BASIC}}===

20 N=ABS(N)

30 C = 0

60 IF N MOD F = 0 THEN C = C + 1 : N = N / F ELSE F = F + 1

70 IF N > 1 THEN GOTO 60

 

==={{header|Minimal BASIC}}===

{{works with|Commodore BASIC|3.5}}

{{works with|Nascom ROM BASIC|4.7}}

10 REM Semiprime

20 PRINT "Enter an integer";

160 PRINT "It is not a semiprime."

170 END

 

==={{header|PureBasic}}===

a.i = 2

c.i = 0

PrintN(#CRLF$ + "--- terminado, pulsa RETURN---"): Input()

CloseConsole()

 

==={{header|Tiny BASIC}}===

INPUT N

IF N < 0 THEN LET N = -N

30 LET C = C + 1

LET N = N / F

 

==={{header|Yabasic}}===

a = 2

c = 0

print i, chr$(9), semiprime$(i)

next i

 

=={{header|Bracmat}}==

When Bracmat is asked to take the square (or any other) root of a number, it does so by first finding the number's prime factors. It can do that for numbers up to 2^32 or 2^64 (depending on compiler and processor).

m n a b

. 2^-64:?m

& !arg^!m

: (#%?a^!m*#%?b^!m|#%?a^!n&!a:?b)

 

Test with numbers < 2^63:

& whl

' ( -1+!u:>2:?u

|

)

 

Output:

 

=={{header|C}}==

 

int semiprime(int n)

 

return 0;

{{out}}

<pre> 4 6 9 10 14 15 21 22 25 26 33 34 35 38 39 46 49 51 55 57 58 62 65 69 74 77 82 85 86 87 91 93 94 95</pre>

 

=={{header|C sharp|C#}}==

static void Main(string[] args)

{

return b == 2;

}

{{out}}

<pre>

 

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

#include <iostream>

 

return 0;

}

{{out}}

<pre>

=={{header|Clojure}}==

{{trans|C}}

(ns example

(:gen-class))

 

(println (filter semi-prime? (range 1 100)))

{{Out}}

<pre>

 

=={{header|Common Lisp}}==

(cond ((> a (isqrt n)) nil)

((zerop (rem n a)) (and (primep a) (primep (/ n a))))

(cond ((> a (isqrt n)) t)

((zerop (rem n a)) nil)

 

Example Usage:

=={{header|Crystal}}==

{{trans|D}}

nf = 0

(2..n).each do |i|

end

 

{{out}}

<pre>1675 -> false

 

Faster version using 'factor' function from [U|Li]nux Core Utilities library.

`factor #{n}`.split(' ').size == 3

end

n = 0xffffffffffffffff_u64 # 2**64 - 1 = 18446744073709551615

{{out}}

<pre>18446744073709551565 -> false

=={{header|D}}==

{{trans|Go}}

auto nf = 0;

foreach (immutable i; 2 .. n + 1) {

foreach (immutable n; 1675 .. 1681)

writeln(n, " -> ", n.semiprime);

{{out}}

<pre>1675 -> false

=={{header|DCL}}==

Given a file primes.txt is the list of primes up to the sqrt(2^31-1), i.e. 46337;

$ if p1 .lt. 2

$ then

$

$ clean:

{{out}}

<pre>$ @factor 6

 

=={{header|EchoLisp}}==

(lib 'math)

(define (semi-prime? n)

(prime-factors 100000000042)

→ (2 50000000021)

 

=={{header|Elixir}}==

def semiprime?(n), do: length(decomposition(n)) == 2

Enum.each(1675..1680, fn n ->

:io.format "~w -> ~w\t~s~n", [n, Prime.semiprime?(n), Prime.decomposition(n)|>Enum.join(" x ")]

 

{{out}}

Another using prime factors from [[Prime_decomposition#Erlang]] :

 

-module(factors).

-export([factors/1,kthfactor/2]).

_ ->

false end.

{out}

<pre>

 

=={{header|ERRE}}==

PROGRAM SEMIPRIME_NUMBER

 

PRINT

END PROGRAM

Output is the same of "C" version.

 

=={{header|F_Sharp|F#}}==

let rec loop currentN candidateFactor numberOfFactors =

if numberOfFactors > 2 then numberOfFactors

|> Seq.choose (fun n -> if isSemiprime n then Some(n) else None)

|> Seq.toList

{{out}}

<pre>[4; 6; 9; 10; 14; 15; 21; 22; 25; 26; 33; 34; 35; 38; 39; 46; 49; 51; 55; 57; 58; 62; 65; 69; 74; 77; 82; 85; 86; 87; 91; 93; 94; 95]

=={{header|Factor}}==

{{works with|Factor|0.98}}

 

 

Displaying the semiprimes under 100:

 

{{out}}

<pre>

 

=={{header|Forth}}==

0 swap dup 2 do

begin dup i mod 0= while i / swap 1+ swap repeat

;

 

{{out}}

<pre>

 

=={{header|Frink}}==

{

factors = factor[n]

 

return sum == 2

 

=={{header|Go}}==

 

import "fmt"

fmt.Println(v, "->", semiprime(v))

}

{{out}}

<pre>

=={{header|Haskell}}==

{{libheader|Data.Numbers.Primes}}

isSemiprime n = (length factors) == 2 && (product factors) == n ||

(length factors) == 1 && (head factors) ^ 2 == n

 

Alternative (and faster) implementation using pattern matching:

isSemiprime n = case (primeFactors n) of

[f1, f2] -> f1 * f2 == n

 

=={{header|Icon}} and {{header|Unicon}}==

 

Works in both languages:

 

procedure main(A)

procedure semiprime(n) # Succeeds and produces the factors only if n is semiprime.

return (2 = *(nf := factors(n)), nf)

 

{{Out}}

Implementation:

 

 

Example use: find all semiprimes less than 100:

 

 

Description: factor the number and count the primes in the factorization, is it 2?

 

Like the Ada example here, this borrows from [[Prime decomposition#Java|Prime decomposition]] and shows the semiprimes below 100 and from 1675 to 1680.

import java.util.ArrayList;

import java.util.List;

}

}

{{out}}

<pre>4 6 9 10 14 15 21 22 25 26 27 33 34 35 38 39 46 49 51 55 57 58 62 65 69 74 77 81 82 85 86 87 91 93 94 95

See e.g. [[Erd%C5%91s-primes#jq]] for a suitable implementation of `is_prime`.

 

# Output: a stream of proper factors (probably unsorted)

def proper_factors:

| any(proper_factors;

is_prime and (($n / .) | (. == $n or is_prime) );

'''Examples'''

(1679, 1680) | "\(.) => \(is_semiprime)"

{{out}}

<pre>

{{works with|Julia|0.6}}

 

issemiprime(n::Integer) = sum(values(factor(n))) == 2

 

{{out}}

=={{header|Kotlin}}==

{{trans|Go}}

 

fun isSemiPrime(n: Int): Boolean {

for (v in 1675..1680)

println("$v ${if (isSemiPrime(v)) "is" else "isn't"} semi-prime")

 

{{out}}

 

=={{header|Ksh}}==

#!/bin/ksh

 

done

echo

{{out}}<pre>

4 6 9 10 14 15 21 22 25 26 33 34 35 38 39 46 49 51 55 57 58 62 65 69 74 77 82 85 86 87 91 93 94 95

 

=={{header|Lingo}}==

div = 2

cnt = 0

end repeat

return cnt=2

 

repeat with i = 1 to 100

if isSemiPrime(i) then res.add(i)

end repeat

 

{{out}}

 

=={{header|Lua}}==

function semiprime (n)

local divisor, count = 2, 0

print(n, semiprime(n))

end

{{out}}

<pre>

 

=={{header|Maple}}==

local fact;

fact := NumberTheory:-Divisors( n ) minus {1, n};

end if;

end proc:

Output:

{ 4,6,9,10,14,15,21,22,25,26,33,34,35,38,39,46,49,51,55,57,58,62,65,69,74,77,82,85,86,87,91,93,94,95 }

 

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

factors = FactorInteger[n] // Transpose;

numfactors = factors[[2]] // Total ;

numfactors == 2

Example use: find all semiprimes less than 100:

{{out}}

<pre>{4, 6, 9, 10, 14, 15, 21, 22, 25, 26, 33, 34, 35, 38, 39, 46, 49, 51,

 

=={{header|MiniScript}}==

divisor = 2

primes = 0

if isSemiprime(i) then results.push i

end for

 

{{output}}

 

=={{header|NewLisp}}==

;;; Practically identical to the EchoLisp solution

(define (semiprime? n)

(while (not (semiprime? x)) (-- x))

(println "Biggest semiprime reachable: " x " = " ((factor x) 0) " x " ((factor x) 1))

{{output}}

<pre>

 

=={{header|Nim}}==

var

i = 2

for k in 1675..1680:

 

{{output}}

=={{header|Objeck}}==

{{trans|Go}}

class SemiPrime {

function : Main(args : String[]) ~ Nil {

return nf = 2;

}

 

Output:

=={{header|Oforth}}==

 

| i |

0 2 n sqrt asInteger for: i [ while(n i /mod swap 0 &=) [ ->n 1+ ] drop ]

 

{{out}}

 

=={{header|PARI/GP}}==

 

A faster version might use trial division and primality testing:

forprime(p=2,97,if(n%p==0, return(isprime(n/p))));

if(isprime(n), return(0));

bigomega(n)==2

 

To get faster, partial factorization can be used. At this time GP does not have access to meaningful partial factorization (though it can get it to some extent through flags on <code>factorint</code>), so this version is in PARI:

issemiprime(GEN n)

{

avma = ltop;

return 0; /* never used */

 

=={{header|Pascal}}==

{{libheader|primTrial}}{{works with|Free Pascal}}

 

{$IFDEF FPC}

{$Mode objfpc}// compiler switch to use result

inc(i);

until i> k;

;output:

<pre>

{{libheader|ntheory}}

With late versions of the ntheory module, we can use <tt>is_semiprime</tt> to get answers for 64-bit numbers in single microseconds.

for ([1..100], [1675..1681], [2,4,99,100,1679,5030,32768,1234567,9876543,900660121]) {

print join(" ",grep { is_semiprime($_) } @$_),"\n";

{{out}}

<pre>4 6 9 10 14 15 21 22 25 26 33 34 35 38 39 46 49 51 55 57 58 62 65 69 74 77 82 85 86 87 91 93 94 95

 

One can also use <tt>factor</tt> in scalar context, which gives the number of factors (like <tt>bigomega</tt> in Pari/GP and <tt>PrimeOmega</tt> in Mathematica). This skips some optimizations but at these small sizes it doesn't matter.

 

While <tt>is_semiprime</tt> is the fastest way, we can do some of its pre-tests by hand, such as:

sub issemi {

my $n = shift;

}

2 == factor($n);

 

=={{header|Phix}}==

<span style="color: #008080;">function</span> <span style="color: #000000;">semiprime</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>

<span style="color: #008080;">return</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">prime_factors</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #004600;">true</span><span style="color: #0000FF;">))==</span><span style="color: #000000;">2</span>

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

<span style="color: #7060A8;">pp</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">filter</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">tagset</span><span style="color: #0000FF;">(</span><span style="color: #000000;">100</span><span style="color: #0000FF;">)&</span><span style="color: #7060A8;">tagset</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1680</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1675</span><span style="color: #0000FF;">),</span><span style="color: #000000;">semiprime</span><span style="color: #0000FF;">),{</span><span style="color: #004600;">pp_IntCh</span><span style="color: #0000FF;">,</span><span style="color: #004600;">false</span><span style="color: #0000FF;">})</span>

{{out}}

<pre>

=={{header|PHP}}==

{{trans|TypeScript}}

<?php

// Semiprime

"It is a semiprime.\n" : "It is not a semiprime.\n");

?>

{{out}}

<pre>

 

=={{header|PicoLisp}}==

(make

(let

(conc (range 1 100) (range 1675 1680)) ) )

{{out}}

<pre>(4 6 9 10 14 15 21 22 25 26 33 34 35 38 39 46 49 51 55 57 58 62 65 69 74 77 82 85 86 87 91 93 94 95 1678 1679)</pre>

 

=={{header|PL/I}}==

/*--------------------------------------------------------------------

* 22.02.2014 Walter Pachl using the is_prime code from

 

End spb;

'''Output:'''

<pre> 900660121 1 is semiprime 30011*30011

 

=={{header|PowerShell}}==

function isPrime ($n) {

if ($n -le 1) {$false}

$OFS = " "

"semiprime form 1 to 100: $(1..100 | where {semiprime $_})"

<b>Output:</b>

<pre>

=={{header|Python}}==

This imports [[Prime decomposition#Python]]

 

def semiprime(n):

return next(d) * next(d) == n

except StopIteration:

 

{{out}}

From Idle:

True

>>> [n for n in range(1,101) if semiprime(n)]

[4, 6, 9, 10, 14, 15, 21, 22, 25, 26, 33, 34, 35, 38, 39, 46, 49, 51, 55, 57, 58, 62, 65, 69, 74, 77, 82, 85, 86, 87, 91, 93, 94, 95]

 

=={{header|Quackery}}==

<code>factors</code> is defined at [http://rosettacode.org/wiki/Factors_of_an_integer#Quackery Factors of an integer].

 

 

say "Semiprimes less than 100:" cr

 

{{out}}

=={{header|Racket}}==

The first implementation considers all pairs of factors multiplying up to the given number and determines if any of them is a pair of primes.

(require math)

 

(for/or ((pair (pair-factorize n)))

(for/and ((el pair))

 

The alternative implementation operates directly on the list of prime factors and their multiplicities. It is approximately 1.6 times faster than the first one (according to some simple tests of mine).

(require math)

 

(= (expt (caar prime-factors) (cadar prime-factors)) n))

(and (= (length prime-factors) 2)

 

=={{header|Raku}}==

(formerly Perl 6)

Here is a naive, grossly inefficient implementation.

not $n.is-prime and

.is-prime given

nok is-semiprime([*] my @f3 = @primes.roll(3)), ~@f3;

nok is-semiprime([*] my @f4 = @primes.roll(4)), ~@f4;

{{out}}

<pre>ok 1 - 17

{{works with|Rakudo|2017.02}}

 

return False if $n.is-prime;

my $factor = find-factor( $n );

 

say 'elapsed seconds: ', now - $start;

{{out}}

<pre>Semiprimes less than 100:

=={{header|REXX}}==

===version 1===

* 20.02.2014 Walter Pachl relying on 'prime decomposition'

* 21.02.2014 WP Clarification: I copied the algorithm created by

z=z%j /*% (percent) is integer divide.*/

end /*while z··· */ /* // ?---remainder integer ÷.*/

'''Output'''

<pre>4 is semiprime 2 2

 

The &nbsp; '''isPrime''' &nbsp; function could be optimized by utilizing an integer square root function instead of testing if &nbsp; '''j*j>x''' &nbsp; for every divisor.

parse arg bot top . /*obtain optional arguments from the CL*/

if bot=='' | bot=="," then bot=random() /*None given? User wants us to guess.*/

else return 0

end /*k*/ /* [↑] see if 2nd factor is prime or ¬*/

{{out|output|text=&nbsp; when using the input of: &nbsp; <tt> -1 &nbsp; 106 </tt>}}

 

 

It gets its speed increase by the use of memoization of the prime numbers found, an unrolled primality (division) check, and other speed improvements.

parse arg bot top . /*obtain optional arguments from the CL*/

if bot=='' | bot=="," then bot=random() /*None given? User wants us to guess.*/

end /*k*/ /* [↑] see if 2nd factor is prime or ¬*/

end /*j*/ /* [↑] J is never a multiple of three.*/

{{out|output|text=&nbsp; is identical to the previous REXX version.}} <br><br>

 

=={{header|Ring}}==

prime = 1679

decomp(prime)

next

return true

 

=={{header|Ruby}}==

# 75.prime_division # Returns the factorization.75 divides by 3 once and by 5 twice => [[3, 1], [5, 2]]

 

p ( 1..100 ).select( &:semi_prime? )

# [4, 6, 9, 10, 14, 15, 21, 22, 25, 26, 33, 34, 35, 38, 39, 46, 49, 51, 55, 57, 58, 62, 65, 69, 74, 77, 82, 85, 86, 87, 91, 93, 94, 95]

 

Faster version using 'factor' function from [U|Li]nux Core Utilities library.

`factor #{n}`.split(' ').size == 3

end

n = 2**72 - 1 #4722366482869645213695

{{out}}

<pre>4722366482869645213645 -> false

 

=={{header|Rust}}==

 

fn isqrt(n: usize) -> usize {

fn test6() {

assert_eq!((2..1_000_000).filter(|&n| is_semiprime(n)).count(), 210_035);

functional version of is_semiprime:

fn iter(x: usize, start: usize, acc: &[usize]) -> Vec<usize> {

if acc.len() > 2 {return acc.to_vec()} // break for semi_prime

}

iter(n, 2, &[]).len() == 2

{{out}}

<pre>

=={{header|Scala}}==

{{works with|Scala 2.9.1}}

 

def isSP(n: Int): Boolean = {

1675 to 1681 foreach {i => println(i+" -> "+isSP(i))}

{{out}}

<pre>4 6 9 10 14 15 21 22 25 26 33 34 35 38 39 46 49 51 55 57 58 62 65 69 74 77 82 85 86 87 91 93 94 95

 

=={{header|Seed7}}==

 

const func boolean: semiPrime (in var integer: n) is func

writeln(v <& " -> " <& semiPrime(v));

end for;

 

{{out}}

=={{header|Sidef}}==

Built-in:

 

User-defined function, with trial division up to a given bound '''B''':

 

with (n.trial_factor(B)) { |f|

}

 

{{out}}

<pre>

=={{header|Swift}}==

 

 

func primes(n: Int) -> AnyGenerator<Int> {

}

return false

 

=={{header|Tcl}}==

{{tcllib|math::numtheory}}

 

proc isSemiprime n {

puts "NOT a semiprime"

}

{{out}}

<pre>

== {{header|TypeScript}} ==

{{trans|ASIC}}

// Semiprime

 

readline.close();

});

{{out}}

<pre>

=={{header|Wren}}==

{{trans|Go}}

if (n < 3) return false

var nf = 0

for (v in 1675..1680) {

System.print("%(v) -> %(semiprime.call(v) ? "is" : "is not") semi-prime")

 

{{out}}

 

=={{header|XPL0}}==

int N, F, C;

[C:= 0; F:= 2;

if Semiprime(N) then

[IntOut(0, N); ChOut(0, ^ )];

 

{{out}}

=={{header|zkl}}==

{{trans|C}}

reg f = 0;

p:=2; while(f < 2 and p*p <= n){

}

return(f + (n > 1) == 2);

{{out}}

<pre>