26
\$\begingroup\$

Surprisingly, I don't think we have a question for determining if a number is semiprime.

A semiprime is a natural number that is the product of two (not necessarily distinct) prime numbers.

Simple enough, but a remarkably important concept.

Given a positive integer, determine if it is a semiprime. Your output can be in any form so long as it gives the same output for any truthy or falsey value. You may also assume your input is reasonably small enough that performance or overflow aren't an issue.

Test cases:

input -> output
1     -> false
2     -> false
3     -> false
4     -> true
6     -> true
8     -> false
30    -> false   (5 * 3 * 2), note it must be EXACTLY 2 (non-distinct) primes
49    -> true    (7 * 7)      still technically 2 primes
95    -> true
25195908475657893494027183240048398571429282126204032027777137836043662020707595556264018525880784406918290641249515082189298559149176184502808489120072844992687392807287776735971418347270261896375014971824691165077613379859095700097330459748808428401797429100642458691817195118746121515172654632282216869987549182422433637259085141865462043576798423387184774447920739934236584823824281198163815010674810451660377306056201619676256133844143603833904414952634432190114657544454178424020924616515723350778707749817125772467962926386356373289912154831438167899885040445364023527381951378636564391212010397122822120720357
      -> true, and go call someone, you just cracked RSA-2048

This is , so standard rules apply!

\$\endgroup\$
  • 4
    \$\begingroup\$ @WheatWizard There's a slightly difference in that that one asks for 3 primes (not a big difference for almost all languages) and it's for distinct primes only (fairly different for some languages). I can discuss it with you in chat if you'd like to continue a more detailed discussion. \$\endgroup\$ – HyperNeutrino Aug 7 '17 at 18:30
  • 2
    \$\begingroup\$ @WheatWizard You raise a good point, but similarly, we already have a bunch of many types of questions, and although, in contrast to what you express, most of them do add significant contribution to their area, this question has enough of a difference that I would believe that it warrants a separate question/post. \$\endgroup\$ – HyperNeutrino Aug 7 '17 at 18:33
  • 2
    \$\begingroup\$ @hyperneutrino looking at the answers on both challenges, it looks like the difference is a single number in the source code, 2 vs 3. I would hardly call that a big difference. \$\endgroup\$ – Sriotchilism O'Zaic Aug 7 '17 at 18:37
  • 2
    \$\begingroup\$ @WheatWizard There is also "distinct" vs "not distinct"... \$\endgroup\$ – HyperNeutrino Aug 7 '17 at 18:40
  • 3
    \$\begingroup\$ @LordFarquaad Just because its a duplicate doesn't mean it is bad. In my mind being a duplicate is a good thing, it means that you are asking a thing that the community finds interesting enough to have already asked about. \$\endgroup\$ – Sriotchilism O'Zaic Aug 7 '17 at 18:50

33 Answers 33

0
\$\begingroup\$

PHP, 75 bytes

<?php for($c=$t=2;$n=&$argv[1]>1;$t++)while($n%$t<1){$c--;$n/=$t;}echo+!$c;

Try it online!

This script is called from the command line with the number being tested as its parameter. It prints out a 1 if the number was a semi-prime, else a 0.

Explanation

<?php

Work through each integer, $t, from 2 up, to see if it's a factor. We need to keep going, dividing by the factors until $n (an alias for $argv[1], the first CLI parameter) reaches 1. (And as there is a 2 to hand, we take the chance to initialize the counter, $c, to 2.)

for ($c = $t = 2; $n = &$argv[1] > 1; $t++)

When we find a factor, we keep using it for as long as we can…

    while ($n % $t < 1) {

…each time deccrementing the factor counter…

        $c--;

…and recalculating our number.

        $n /= $t;
    }

When we reach the end, the counter can only be 0 if there were 2 factors. We ‘not’ the number, but this converts it to a boolean, so we use + to make it into 1 (the number was a semi-prime) or 0 (it wasn’t).

echo +!$c;
\$\endgroup\$
0
\$\begingroup\$

Braingolf, 8 bytes

pl2e1:0|

Try it online!

\$\endgroup\$
0
\$\begingroup\$

APL(NARS), 7 chars, 14 bytes

{2=≢π⍵}

test:

  f←{2=≢π⍵}
  f¨1 2 3 4 6 8 30 49 95
0 0 0 1 1 0 0 1 1 
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.