Est-ce un semi-premier?

26

Étonnamment, je ne pense pas que nous ayons une question de pour déterminer si un nombre est à mi-temps .

Un semi-premier est un nombre naturel qui est le produit de deux nombres premiers (pas nécessairement distincts).

Assez simple, mais un concept remarquablement important.

Étant donné un entier positif, déterminez s'il s'agit d'un semi-premier. Votre sortie peut être sous n'importe quelle forme tant qu'elle donne la même sortie pour toute valeur véridique ou falsey. Vous pouvez également supposer que votre entrée est suffisamment petite pour que les performances ou le débordement ne soient pas un problème.

Cas de test:

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

Il s'agit de , donc les règles standard s'appliquent!

Lord Farquaad
la source
4
@WheatWizard Il y a une légère différence en ce que l'on demande 3 nombres premiers (pas une grande différence pour presque toutes les langues) et c'est uniquement pour des nombres premiers distincts (assez différents pour certaines langues). Je peux en discuter avec vous dans le chat si vous souhaitez poursuivre une discussion plus détaillée.
HyperNeutrino
2
@WheatWizard Vous soulevez un bon point, mais de même, nous avons déjà un tas de nombreux types de questions, et bien que, contrairement à ce que vous exprimez, la plupart d'entre elles apportent une contribution significative à leur domaine, cette question a suffisamment de différence que je pense que cela mérite une question / un message séparé.
HyperNeutrino
2
@hyperneutrino regardant les réponses sur les deux défis, il semble que la différence soit un seul numéro dans le code source, 2 contre 3. Je dirais à peine que c'est une grande différence.
Wheat Wizard
2
@WheatWizard Il y a aussi "distinct" vs "non distinct" ...
HyperNeutrino
3
@LordFarquaad Ce n'est pas parce qu'il s'agit d'un doublon qu'il est mauvais. Dans mon esprit, être un doublon est une bonne chose, cela signifie que vous demandez une chose que la communauté trouve suffisamment intéressante pour avoir déjà posé des questions.
Wheat Wizard

Réponses:

19

Brachylog , 2 octets

Fondamentalement, un port de la réponse de Fatalize au défi du numéro Sphenic.

ḋĊ

Essayez-le en ligne!

Comment?

ḋĊ - implicitly takes input
ḋ  - prime factorisation (with duplicates included)
 Ċ - is a couple
Jonathan Allan
la source
1
La bonne langue pour le travail en effet: P
HyperNeutrino
2
@Uriel Ċest en fait une liste intégrée de deux variables; étant un langage déclaratif, la sortie est, par défaut, un test de satisfaction (par exemple , seul produirait true.des entiers non négatifs).
Jonathan Allan
Comment sont ces 2 octets?
harold
1
@harold Je viens de mettre à jour pour faire des "octets" dans le lien d'en-tête vers la page de code de Brachylog. Un vidage hexadécimal serait c6 eb.
Jonathan Allan
16

Décortiquer , 4 octets

Regardez ma pas Unicode!

=2Lp

Essayez-le en ligne!

Comment?

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

Mathematica, 16 octets

PrimeOmega@#==2&

PrimeOmega compte le nombre de facteurs premiers, en comptant la multiplicité.

ngenisis
la source
1
Dang, il y a une fonction intégrée?
JungHwan Min
1
@JungHwanMin Si seulement il y avaitSemiprimeQ
ngenisis
Agréable. Je ne savais pasPrimeOmega
DavidC
7

Pyth , 4 octets

q2lP

Suite de tests .


Comment?

q2lPQ     - Q is implicit input.

q2        - Is equal to 2?
    lPQ   - The length of the prime factors of the input.
M. Xcoder
la source
Bon sang, des constructions plus courtes! :(
HyperNeutrino
7

Python 3 , 54 octets

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

Essayez-le en ligne!

Le Verson précédent avait quelques problèmes d' arrondi sur un grand nombre de cube ( 125, 343, etc.)
Il calcule la quantité de diviseurs (non seulement les nombres premiers), si elle a 1ou 2il retourne True.
La seule exception est lorsqu'un nombre a plus de deux facteurs premiers mais seulement deux diviseurs. Dans ce cas, c'est un cube parfait d'un nombre premier (ses diviseurs sont sa racine cubique et sa racine cubique au carré). x**3==ncouvrira ce cas, l'ajout d'un à l'entrée racine du cube pousse la somme jusqu'à un nombre de 3 et arrête le faux positif. remercie Jonathan Allan d'avoir écrit avec cette belle explication

Barre
la source
Ceci prétend que 8 est semi
prime
n**(1/3)%1>0<sum...devrait marcher.
Dennis
1
@xnor l'a corrigé.
Rod
A fait un petit montage (par exemple 6 cubes a beaucoup plus de diviseurs)
Jonathan Allan
6

Rubis , 56 48 octets

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

Essayez-le en ligne!

Comment ça marche:

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

Merci Value Ink pour l'idée d'avoir économisé 8 octets.

GB
la source
Pourquoi ne pas simplement ccommencer à 0 et compter, au lieu d'en faire un tableau auquel vous ajoutez tous les facteurs? De cette façon, vous supprimez le besoin d'utiliser sizeà la fin
Value Ink
Vous avez raison, c'est parce que j'ai écrit la fonction de factorisation pour un autre défi et je l'ai réutilisée ici.
GB
5

Mathematica, 31 29 octets

Tr[Last/@FactorInteger@#]==2&
JungHwan Min
la source
4

Neim , 4 octets

𝐏𝐥δ𝔼

Essayez-le en ligne!

Okx
la source
Pouvez-vous expliquer comment cela fait 4 octets? ... Je suis totalement confus.
M. Xcoder
Lol je viens d'avoir ça
HyperNeutrino
@ Mr.Xcoder Neim a une page de codes personnalisée
JungHwan Min
@ Mr.Xcoder En utilisant la c'est codepage, Neim 𝐏, 𝐥, δet 𝔼comme mono-octets.
HyperNeutrino
@HyperNeutrino Je viens de brouiller les 2 un peu, et maintenant c'est la seule réponse sans 2 :)
Okx
4

Python 2 , 67 octets

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]

Essayez-le en ligne!

-10 octets grâce à @JonathanAllan!

Le mérite de l'algorithme de factorisation Prime revient à Dennis (dans la version initiale)

M. Xcoder
la source
Avez-vous utilisé le code de la réponse de Dennis ? Si c'est le cas, vous devriez donner du crédit.
2017 totalement humain
1
@totallyhuman Oh ouais, désolé. Je l'ai utilisé dans 2 réponses différentes aujourd'hui et je lui ai rendu hommage dans l'une d'entre elles, mais j'ai oublié de le faire ici encore une fois. Merci d'avoir repéré ça!
M. Xcoder
1
67 octets
Jonathan Allan
@JonathanAllan Wow, merci beaucoup!
M. Xcoder
55 octets
Halvard Hummel
4

JavaScript (ES6), 47 octets

Renvoie un booléen.

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

Démo

Arnauld
la source
4

Mathematica 32 octets

Merci à ngenesis pour 1 octet enregistré

Tr@FactorInteger[#][[;;,2]]==2&
DavidC
la source
1
Enregistrez un octet en utilisant ;;au lieu de All.
ngenisis
3

Gelée , 5 octets

ÆfL=2

Essayez-le en ligne!

Explication

ÆfL=2  Main link
Æf     Prime factors
  L    Length
   =   Equals
    2  2
HyperNeutrino
la source
3

05AB1E, 4 octets

Òg2Q

Essayez-le en ligne!

Comment?

Ò       prime factors list (with duplicates)
 g      length
   Q    equal to
  2     2
Uriel
la source
3

Dyalog APL, 18 octets

⎕CY'dfns'
2=≢3pco⎕

Essayez-le en ligne!

Comment?

⎕CY'dfns' - importer pco

3pco⎕ - courir pco en entrée avec l'argument de gauche 3 (facteurs premiers)

2=≢ - longueur = 2?

Uriel
la source
3

Gaia , 4 octets

ḍl2=

4 octets semble être une longueur commune, je me demande pourquoi ...: P

Essayez-le en ligne!

Explication

ḍ     Prime factors
 l    Length
  2=  Equals 2?
Chat d'affaires
la source
4 octets semble être une longueur commune, je me demande pourquoi ... - Probablement parce que toutes les réponses sont des facteurs premiers, la longueur est égale à 2?
M. Xcoder
@MrXcoder Oui, exactement
Business Cat
Dont
4 est également le premier semi-premier. Effrayant!
Neil
3

Python avec SymPy 1.1.1 ,  57  44 octets

-13 octets grâce à alephalpha (utilisez 1.1.1's primeomega)

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

Essayez-le en ligne!

Jonathan Allan
la source
lambda n:primeomega(n)==2
alephalpha
Ah ça me rappelle de passer à la version 1.0, merci!
Jonathan Allan
2

Rubis , 35 + 8 = 43 octets

Utilise le -rprimedrapeau pour déverrouiller la prime_divisionfonction.

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

Essayez-le en ligne!

Encre de valeur
la source
2

Java 8, 69 61 octets

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

-8 octets grâce à @Nevay .

Essayez-le ici.

Kevin Cruijssen
la source
1
Vous pouvez supprimer l'instruction else (qui pourrait être else++r;) pour économiser 8 octets 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 octets

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

Essayez-le en ligne!

Tout le crédit à la réponse de xnor pour le code de factorisation premier d'origine.

totalement humain
la source
1

C #, 112 octets

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));}

Avec la mise en forme appliquée:

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));
}

Et comme programme de test:

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 ();
        }
    }
}

Qui a la sortie:

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
la source
1

Rétine , 45 octets

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

Essayez-le en ligne! Le lien inclut des cas de test. Explication:

.+
$*

Convertissez en unaire.

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

Essayez de trouver deux facteurs.

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

Assurez-vous que les deux facteurs sont primordiaux.

;

Assurez-vous que deux facteurs ont été trouvés.

Neil
la source
1

Python 2, 90 octets

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

fprend un entier nsupérieur ou égal à 1, renvoie booléen.

Essayez-le en ligne!

Cas de test:

>>> 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
la source
1

J , 6 octets

5 octets fonctionneront de manière unique:

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

Je crois que j'en ai besoin de six lorsque je définis la fonction:

   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
Danois
la source
1

Japt , 6 5 octets

k ʥ2

Testez-le en ligne


Explication

Fait à peu près la même chose que la plupart des autres réponses: kobtient le tableau des facteurs premiers, Êobtient sa longueur et ¥vérifie l'égalité avec 2.

Hirsute
la source
÷k o)jfonctionne aussi, malheureusement c'est la même longueur :-(
ETHproductions
0

Perl 6 , 43 octets

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

Essayez-le en ligne!

fest le plus petit facteur supérieur à 1 de l'argument d'entrée $_, ou Nilsi $_est 1. La valeur de retour de la fonction est vraie si fest vraie (c'est-à-dire pasNil ) ET l'argument d'entrée divisé par le facteur est premier.

Si $_lui-même est premier, alors fsera égal à $_, et $_ / fest 1, ce qui n'est pas premier, donc la formule fonctionne dans ce cas également.

Sean
la source