26

Surpreendentemente, não acho que tenhamos uma pergunta sobre código de golfe para determinar se um número é semiprime .

Um semiprime é um número natural que é o produto de dois números primos (não necessariamente distintos).

Simples o suficiente, mas um conceito notavelmente importante.

Dado um número inteiro positivo, determine se é um semiprime. Sua saída pode ser de qualquer forma, desde que ela seja igual para qualquer valor de verdade ou falsey. Você também pode assumir que sua entrada é razoavelmente pequena o suficiente para que o desempenho ou o excesso não sejam um problema.

Casos de teste:

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

Isso é código-golfe , então as regras padrão se aplicam!

code-golf sequence Lord Farquaad
fonte

4

@WheatWizard Há uma pequena diferença no fato de que se pede 3 números primos (não uma grande diferença para quase todos os idiomas) e é apenas para números primos distintos (bastante diferentes para alguns idiomas). Posso discutir isso com você no bate-papo, se você quiser continuar uma discussão mais detalhada.

HyperNeutrino

2

@WheatWizard Você levanta um bom argumento, mas, da mesma forma, já temos muitos tipos de perguntas e, embora, ao contrário do que você expressa, a maioria adicione uma contribuição significativa à sua área, essa pergunta tem bastante diferença. que eu acredito que merece uma pergunta / postagem separada.

HyperNeutrino

2

@hyperneutrino, olhando as respostas para os dois desafios, parece que a diferença é um número único no código-fonte, 2 vs 3. Eu dificilmente chamaria isso de uma grande diferença.

Wheat Wizard

2

@WheatWizard Há também "distinta" vs "não distinta" ...

HyperNeutrino

3

@LordFarquaad Só porque é uma duplicata não significa que é ruim. Em minha opinião, ser uma duplicata é uma coisa boa, significa que você está perguntando algo que a comunidade acha interessante o suficiente para já ter perguntado.

Wheat Wizard

19

Braquilog , 2 bytes

Basicamente, um exemplo da resposta de Fatalize ao desafio do número esfênico.

ḋĊ

Experimente online!

Quão?

ḋĊ - implicitly takes input
ḋ  - prime factorisation (with duplicates included)
 Ċ - is a couple

Jonathan Allan
fonte

1

Linguagem correta para o trabalho: P

HyperNeutrino

2

@Uriel Ċé na verdade uma lista interna de duas variáveis; por ser uma linguagem declarativa, a saída é, por padrão, um teste de satisfação (por exemplo, ḋpor si só resultaria true.em números inteiros não negativos).

Jonathan Allan

Como são esses 2 bytes?

quer

1

@harold Acabei de atualizar para criar "bytes" no link do cabeçalho da página de código do Brachylog. Um dump hexadecimal seria c6 eb.

Jonathan Allan

16

Casca , 4 bytes

_{Olha, não sou Unicode!}

=2Lp

Experimente online!

Quão?

=2Lp - a one input function
   p - prime factorisation (with duplicates included)
  L  - length
=2   - equals 2?

Jonathan Allan
fonte

8

Mathematica, 16 bytes

PrimeOmega@#==2&

PrimeOmega conta o número de fatores primos, contando a multiplicidade.

ngenisis
fonte

1

Dang, há um embutido?

JungHwan Min 8/08/17

1

@JungHwanMin Se ao menos houvesseSemiprimeQ

ngenisis 08/08

Agradável. Eu não sabia sobrePrimeOmega

DavidC

7

Pitão , 4 bytes

q2lP

Conjunto de teste .

Quão?

q2lPQ     - Q is implicit input.

q2        - Is equal to 2?
    lPQ   - The length of the prime factors of the input.

Mr. Xcoder
fonte

Droga, construções mais curtas! :(

HyperNeutrino

7

Python 3 , 54 bytes

lambda n:0<sum((n%x<1)+(x**3==n)for x in range(2,n))<3

Experimente online!

^{O verson anterior teve alguns problemas de arredondamento em números grandes de cubos ( 125, 343etc).}
Calcula a quantidade de divisores (não apenas primos), se houver 1ou 2retornar True.
A única exceção é quando um número tem mais de dois fatores primos, mas apenas dois divisores. Nesse caso, é um cubo perfeito de primo (seus divisores são a raiz do cubo e a raiz do cubo ao quadrado). x**3==nabordará esse caso, adicionar um à entrada raiz do cubo eleva a soma até uma contagem de 3 e interrompe o falso positivo. ^{obrigado Jonathan Allan por escrever com esta bela explicação}

Cajado
fonte

Isto afirma que 8 é semiprime

xnor

n**(1/3)%1>0<sum...Deveria trabalhar.

Dennis

1

@xnor corrigiu.

Rod

Fez uma pequena edição (por exemplo, 6 cubos tem muitos mais divisores)

Jonathan Allan

6

Ruby , 56 48 bytes

->x{r=c=2;0while x%r<1?(x/=r;c-=1):x>=r+=1;c==0}

Experimente online!

Como funciona:

->x{                    # Lambda function
    r=c=2;              # Starting from r=2, c=2
    0 while             # Repeat (0 counts as a nop)
        x%r<1? (        # If x mod r == 0
            x/=r:       # Divide x by r
            c-=1        # decrease c
        ):              # else
            x>=r+=1     # increase r, terminate if r>x 
    );
    c==0                # True if we found 2 factors
}

Agradecemos ao Value Ink pela ideia que salvou 8 bytes.

GB
fonte

Por que não ccomeçar com 0 e contar, em vez de torná-lo um array ao qual você adiciona todos os fatores? Dessa forma, você elimina a necessidade de usar sizeno final

Value Ink

Você está certo, é porque escrevi a função de fatoração para outro desafio e a reutilizei aqui.

GB

5

Mathematica, 31 29 bytes

Tr[Last/@FactorInteger@#]==2&

JungHwan Min
fonte

4

Neim , 4 bytes

𝐏𝐥δ𝔼

Experimente online!

Okx
fonte

Você pode explicar como isso é 4 bytes? ... Estou totalmente confuso.

Mr. Xcoder

Lol eu só tinha este

HyperNeutrino

@ Mr.Xcoder Neim tem um código personalizado páginas

JungHwan Min

@ Mr.Xcoder usando o código Neim, isto é 𝐏, 𝐥, δ, e 𝔼como únicos-bytes.

HyperNeutrino

@HyperNeutrino Eu apenas ofuscado a 2 um pouco, e agora esta é a única resposta sem 2 :)

Okx

4

Python 2 , 67 bytes

lambda k:f(k)==2
f=lambda n,k=2:n/k and(f(n,k+1),1+f(n/k,k))[n%k<1]

Experimente online!

-10 bytes graças a @JonathanAllan!

O crédito para o algoritmo de fatoração Prime vai para Dennis (na versão inicial)

Mr. Xcoder
fonte

Você usou o código da resposta de Dennis ? Nesse caso, você deve dar crédito.

totallyhuman

1

@totallyhuman Oh sim, desculpe. Usei-o em duas respostas diferentes hoje e dei crédito a ele em uma delas, mas esqueci de fazer isso aqui mais uma vez. Obrigado por descobrir isso!

Mr. Xcoder

1

67 bytes

Jonathan Allan

@ JonathanAllan Wow, muito obrigado!

Mr. Xcoder

55 bytes

Halvard Hummel

4

JavaScript (ES6), 47 bytes

Retorna um booleano.

n=>(k=1)==(d=n=>++k<n?n%k?d(n):d(n/k--)+1:0)(n)

Demo

Mostrar snippet de código

let f =

n=>(k=1)==(d=n=>++k<n?n%k?d(n):d(n/k--)+1:0)(n)

console.log(
  [...Array(200).keys()].filter(f).join`, `
)

Expandir snippet

Arnauld
fonte

4

Mathematica 32 bytes

Graças ao ngenesis por 1 byte salvo

Tr@FactorInteger[#][[;;,2]]==2&

DavidC
fonte

1

Salve um byte usando em ;;vez de All.

Ngenisis

3

Gelatina , 5 bytes

ÆfL=2

Experimente online!

Explicação

ÆfL=2  Main link
Æf     Prime factors
  L    Length
   =   Equals
    2  2

HyperNeutrino
fonte

3

Na verdade , 4 bytes

ol2=

Experimente online!

Mr. Xcoder
fonte

3

05AB1E, 4 bytes

Òg2Q

Experimente online!

Quão?

Ò       prime factors list (with duplicates)
 g      length
   Q    equal to
  2     2

Uriel
fonte

3

MATL, 5 bytes

Yfn2=

Experimente online!

Explicação

Yf - Fatores principais.
n - Comprimento.
2= - é igual a 2?

Mr. Xcoder
fonte

3

Dyalog APL, 18 bytes

⎕CY'dfns'
2=≢3pco⎕

Experimente online!

Quão?

⎕CY'dfns' - importação pco

3pco⎕- executado pcona entrada com argumento esquerdo 3 (fatores primos)

2=≢ - comprimento = 2?

Uriel
fonte

3

Gaia , 4 bytes

ḍl2=

4 bytes parece ser um comprimento comum, gostaria de saber por que ...: P

Experimente online!

Explicação

ḍ     Prime factors
 l    Length
  2=  Equals 2?

Gato de negócios
fonte

4 bytes parece ser um tamanho comum, eu me pergunto por que ... - Provavelmente porque todas as respostas são fatores primos, o comprimento é igual a 2?

Xcoder

@MrXcoder Sim, exatamente

Business Cat

4 dos quais são meus BTW> _>

Sr. Xcoder 08/08

4 também é o primeiro semiprime. Assustador!

Neil

3

Python com SymPy 1.1.1 , 57 44 bytes

-13 bytes graças a alefhalpha (use 1.1.1's primeomega)

from sympy import*
lambda n:primeomega(n)==2

Experimente online!

Jonathan Allan
fonte

lambda n:primeomega(n)==2

alephalpha

Ah, isso me lembra de atualizar da 1.0, obrigado!

Jonathan Allan

3

R , 67 bytes

c=0;n=scan();for(p in(1:n)[-1:-2]-1)while(n%%p<1){c=c+1;n=n/p};c==2

Experimente online!

Freira Furada
fonte

2

Ruby , 35 + 8 = 43 bytes

Usa o -rprimesinalizador para desbloquear a prime_divisionfunção.

->n{n.prime_division.sum(&:pop)==2}

Experimente online!

Value Ink
fonte

2

Java 8, 69 61 bytes

n->{int r=1,c=2;for(;r++<n;)for(;n%r<1;n/=r)c--;return c==0;}

-8 bytes graças a @Nevay .

Experimente aqui.

Kevin Cruijssen
fonte

1

Você pode remover a instrução else (que poderia ser else++r;) para salvar 8 bytes n->{int r=1,c=2;for(;r++<n;)for(;n%r<1;n/=r)c--;return c==0;}.

Nevay

1

Python 2 , 75 65 bytes

lambda n:g(n)==2
g=lambda n,i=2:n/i and[g(n,i+1),1+g(n/i)][n%i<1]

Experimente online!

Todo o crédito à resposta da xnor para o código de fatoração principal original.

totalmente humano
fonte

1

C #, 112 bytes

n=>{var r=Enumerable.Range(2,n);var l=r.Where(i=>r.All(x=>r.All(y=>y*x!=i)));return l.Any(x=>l.Any(y=>y*x==n));}

Com a formatação aplicada:

n =>
{
    var r = Enumerable.Range (2, n);
    var l = r.Where (i => r.All (x => r.All (y => y * x != i)));
    return l.Any (x => l.Any (y => y * x == n));
}

E como programa de teste:

using System;
using System.Linq;


namespace S
{
    class P
    {
        static void Main ()
        {
            var f = new Func<int, bool> (
                n =>
                {
                    var r = Enumerable.Range (2, n);
                    var l = r.Where (i => r.All (x => r.All (y => y * x != i)));
                    return l.Any (x => l.Any (y => y * x == n));
                }
            );

            for (var i = 0; i < 100; i++)
                Console.WriteLine ($"{i} -> {f (i)}");
            Console.ReadLine ();
        }
    }
}

Qual tem a saída:

0 -> False
1 -> False
2 -> False
3 -> False
4 -> True
5 -> False
6 -> True
7 -> False
8 -> False
9 -> True
10 -> True
11 -> False
12 -> False
13 -> False
14 -> True
15 -> True
16 -> False
17 -> False
18 -> False
19 -> False
20 -> False
21 -> True
22 -> True
23 -> False
24 -> False
25 -> True
26 -> True
27 -> False
28 -> False
29 -> False
30 -> False
31 -> False
32 -> False
33 -> True
34 -> True
35 -> True
36 -> False
37 -> False
38 -> True
39 -> True
40 -> False
41 -> False
42 -> False
43 -> False
44 -> False
45 -> False
46 -> True
47 -> False
48 -> False
49 -> True
50 -> False
51 -> True
52 -> False
53 -> False
54 -> False
55 -> True
56 -> False
57 -> True
58 -> True
59 -> False
60 -> False
61 -> False
62 -> True
63 -> False
64 -> False
65 -> True
66 -> False
67 -> False
68 -> False
69 -> True
70 -> False
71 -> False
72 -> False
73 -> False
74 -> True
75 -> False
76 -> False
77 -> True
78 -> False
79 -> False
80 -> False
81 -> False
82 -> True
83 -> False
84 -> False
85 -> True
86 -> True
87 -> True
88 -> False
89 -> False
90 -> False
91 -> True
92 -> False
93 -> True
94 -> True
95 -> True
96 -> False
97 -> False
98 -> False
99 -> False

MetaColon
fonte

1

Pari / GP , 17 bytes

n->bigomega(n)==2

Experimente online!

alefalpha
fonte

1

Retina , 45 bytes

.+
$*
^(11+)(\1)+$
$1;1$#2$*
A`\b(11+)\1+\b
;

Experimente online! O link inclui casos de teste. Explicação:

.+
$*

Converta para unário.

^(11+)(\1)+$
$1;1$#2$*

Tente encontrar dois fatores.

A`\b(11+)\1+\b

Assegure-se de que ambos os fatores sejam primos.

Garanta que dois fatores foram encontrados.

Neil
fonte

1

Python 2, 90 bytes

def g(x,i=2):
 while x%i:i+=1
 return i
def f(n,l=0):
 while 1%n:l+=1;n/=g(n)
 return l==2

fleva um número inteiro nmaior ou igual a1 , retorna booleano.

Experimente online!

Casos de teste:

>>> f(1)
False
>>> f(2)
False
>>> f(3)
False
>>> f(4)
True
>>> f(6)
True
>>> f(8)
False
>>> f(30)
False
>>> f(49)
True
>>> f(95)
True

nog642
fonte

1

J , 6 bytes

5 bytes funcionarão como únicos:

   2=#q: 8
0
   2=#q: 9
1

Acredito que preciso de seis quando defino a função:

   semiprime =. 2=#@q:
   (,. semiprime) 1 + i. 20
 1 0
 2 0
 3 0
 4 1
 5 0
 6 1
 7 0
 8 0
 9 1
10 1
11 0
12 0
13 0
14 1
15 1
16 0
17 0
18 0
19 0
20 0

dinamarquês
fonte

1

Pyke , 5 bytes

Pl02q

Experimente aqui!

Mr. Xcoder
fonte

1

Japonês , 6 5 bytes

k Ê¥2

Teste on-line

Explicação

Faz praticamente o mesmo que a maioria das outras respostas: kobtém a matriz de fatores primos, Êobtém seu comprimento e ¥verifica a igualdade com 2.

Shaggy
fonte

÷k o)jtambém funciona, infelizmente, é do mesmo comprimento :-(

ETHproductions

0

Perl 6 , 43 bytes

{my \f=first $_%%*,2..$_;?f&&is-prime $_/f}

Experimente online!

fé o menor fator maior que 1 do argumento de entrada $_ou Nilse $_é 1. O valor de retorno da função é verdadeiro se ffor verdadeiro (ou seja, nãoNil ) E o argumento de entrada dividido pelo fator é primo.

Se $_ele próprio é primo, então fserá igual a $_, e $_ / fé 1, o que não é primo, portanto, a fórmula funciona nesse caso também.

Sean
fonte

É um semiprime?

Respostas:

Braquilog , 2 bytes

Quão?

Casca , 4 bytes

Quão?

Mathematica, 16 bytes

Pitão , 4 bytes

Quão?

Python 3 , 54 bytes

Ruby , 56 48 bytes

Como funciona:

Mathematica, 31 29 bytes

Neim , 4 bytes

Python 2 , 67 bytes

JavaScript (ES6), 47 bytes

Demo

Mathematica 32 bytes

Gelatina , 5 bytes

Explicação

Na verdade , 4 bytes

05AB1E, 4 bytes

MATL, 5 bytes

Explicação

Dyalog APL, 18 bytes

Gaia , 4 bytes

Explicação

Python com SymPy 1.1.1 , 57 44 bytes

R , 67 bytes

Ruby , 35 + 8 = 43 bytes

Java 8, 69 61 bytes

Python 2 , 75 65 bytes

C #, 112 bytes

Pari / GP , 17 bytes

Retina , 45 bytes

Python 2, 90 bytes

J , 6 bytes

Pyke , 5 bytes

Japonês , 6 5 bytes

Explicação

Perl 6 , 43 bytes