Czy to semiprime?

26

Zaskakujące, nie wydaje mi się, abyśmy mieli pytanie w golfa w celu ustalenia, czy liczba jest półpierwszą .

Semiprime jest liczbą naturalną, która jest iloczynem dwóch (niekoniecznie odrębnych) liczb pierwszych.

Dość prosta, ale niezwykle ważna koncepcja.

Biorąc pod uwagę dodatnią liczbę całkowitą, określ, czy jest to wartość półpierwsza. Twój wynik może być w dowolnej formie, pod warunkiem, że daje to samo wyjście dla dowolnej wartości prawdziwej lub falsey. Możesz również założyć, że Twój wkład jest wystarczająco mały, aby wydajność lub przepełnienie nie stanowiły problemu.

Przypadki testowe:

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

To jest golf golfowy , więc obowiązują standardowe zasady!

code-golf  sequence 
— Lord Farquaad
źródło
4
@WheatWizard Istnieje niewielka różnica w tym, że prosi się o 3 liczby pierwsze (nie jest to duża różnica w prawie wszystkich językach) i dotyczy tylko różnych liczb pierwszych (dość różne w przypadku niektórych języków). Mogę omówić to z tobą na czacie, jeśli chcesz kontynuować bardziej szczegółową dyskusję.
— HyperNeutrino,
2
@WheatWizard Podnosisz dobrą rację, ale podobnie, mamy już wiele różnych rodzajów pytań i chociaż, w przeciwieństwie do tego, co wyrażasz, większość z nich wnosi znaczący wkład w ich obszar, to pytanie ma wystarczającą różnicę wierzę, że uzasadnia to odrębne pytanie / post.
— HyperNeutrino,
2
@hyperneutrino, patrząc na odpowiedzi na oba wyzwania, wygląda na to, że różnica to pojedynczy numer w kodzie źródłowym, 2 vs 3. Nie nazwałbym tego dużą różnicą.
— Wheat Wizard
2
@WheatWizard Istnieje również „wyraźny” vs „nie wyraźny” ...
— HyperNeutrino
3
@ LordFarquaad Tylko dlatego, że jest duplikatem, nie oznacza, że ​​jest zły. Moim zdaniem bycie duplikatem jest dobrą rzeczą, oznacza to, że pytasz o coś, co społeczność uzna za wystarczająco interesujące, aby o to zapytać.
— Wheat Wizard

Odpowiedzi:

19

Brachylog , 2 bajty

Zasadniczo port od odpowiedzi Fatalize na wyzwanie liczby Sphenic.

ḋĊ

Wypróbuj online!

W jaki sposób?

ḋĊ - implicitly takes input
ḋ  - prime factorisation (with duplicates included)
 Ċ - is a couple
— Jonathan Allan
źródło
1
Właściwie odpowiedni język do pracy: P
— HyperNeutrino,
2
@Uriel Ċto właściwie wbudowana lista dwóch zmiennych; ponieważ jest językiem deklaratywnym, dane wyjściowe są domyślnie testem satysfakcji (np. ḋsame w sobie byłyby wynikiem true.dla liczb całkowitych nieujemnych).
— Jonathan Allan,
Jak tam te 2 bajty?
— Harold
1
@harold Właśnie zaktualizowałem, aby utworzyć „bajty” w łączu nagłówka do strony kodowej Brachylog. Byłby zrzut heksowy c6 eb.
— Jonathan Allan,
8

Mathematica, 16 bajtów

PrimeOmega@#==2&

PrimeOmega zlicza liczbę czynników pierwszych, licząc wielokrotność.

— ngenisis
źródło
1
Dang, jest wbudowany?
— JungHwan Min
1
@JungHwanMin Gdyby tylko byłSemiprimeQ
— ngenisis
Miły. Nie wiedziałem oPrimeOmega
— DavidC
7

Python 3 , 54 bajty

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

Wypróbuj online!

Poprzednie verson miał kilka problemów na zaokrąglenie licznie Cube ( 125, 343itp)
to oblicza ilość dzielników (nie tylko liczby pierwsze), jeżeli ma 1lub 2powraca True.
Jedynym wyjątkiem jest sytuacja, gdy liczba ma więcej niż dwa czynniki pierwsze, ale tylko dwa dzielniki. W tym przypadku jest to idealna kostka liczby pierwszej (jej dzielnikami jest pierwiastek sześcianu, a pierwiastek sześcianu podniesiony do kwadratu). x**3==nobejmie ten przypadek, dodanie jednego do wpisu głównego kostki wypycha sumę do liczby 3 i zatrzymuje fałszywie dodatni. dziękuję Jonathanowi Allanowi za pisanie z tym pięknym wyjaśnieniem

— Pręt
źródło
Twierdzenie 8 to semiprime
— xnor
n**(1/3)%1>0<sum...powinno działać.
— Dennis,
1
@xnor naprawił to.
— Rod
Dokonałem drobnej edycji (np. 6 kostek ma znacznie więcej dzielników)
— Jonathan Allan
6

Rubin , 56 48 bajtów

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

Wypróbuj online!

Jak to działa:

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

Dzięki Value Ink za pomysł, który oszczędził 8 bajtów.

— GB
źródło
Dlaczego nie czacząć od zera i policzyć, zamiast uczynić z niego tablicę, do której dodasz wszystkie czynniki? W ten sposób eliminujesz potrzebę użycia sizena końcu
— Value Ink
Masz rację, ponieważ napisałem funkcję faktoryzacji dla innego wyzwania i wykorzystałem ją tutaj.
— GB
4

Python 2 , 67 bajtów

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]

Wypróbuj online!

-10 bajtów dzięki @JonathanAllan!

Uznanie za algorytm faktoryzacji Prime otrzymuje Dennis (w wersji początkowej)

— Pan Xcoder
źródło
Czy używałeś kodu z odpowiedzi Dennisa ? Jeśli tak, powinieneś przyznać kredyt.
— całkowicie ludzki,
1
@totallyhuman Oh tak, przepraszam. Użyłem go dzisiaj w 2 różnych odpowiedziach i przypisałem mu uznanie w jednej z nich, ale znowu zapomniałem to zrobić. Dzięki za wykrycie tego!
— Pan Xcoder,
1
— Jonathan Allan,
@JathanathanAllan Wow, wielkie dzięki!
— Pan Xcoder,
— Halvard Hummel
4

JavaScript (ES6), 47 bajtów

Zwraca wartość logiczną.

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

Próbny

Pokaż fragment kodu

— Arnauld
źródło
4

Mathematica 32 bajty

Dzięki ngenesis zapisano 1 bajt

Tr@FactorInteger[#][[;;,2]]==2&
— DavidC
źródło
1
Zaoszczędź jeden bajt, używając ;;zamiast All.
— ngenisis,
3

Dyalog APL, 18 bajtów

⎕CY'dfns'
2=≢3pco⎕

Wypróbuj online!

W jaki sposób?

⎕CY'dfns' - import pco

3pco⎕- uruchamiany pcona wejściu z lewym argumentem 3 (czynniki pierwsze)

2=≢ - długość = 2?

— Uriel
źródło
3

Gaia , 4 bajty

ḍl2=

4 bajty wydają się być wspólną długością, zastanawiam się, dlaczego ...: P

Wypróbuj online!

Wyjaśnienie

ḍ     Prime factors
 l    Length
  2=  Equals 2?
— Business Cat
źródło
4 bajty wydają się być wspólną długością, zastanawiam się, dlaczego ... - Prawdopodobnie dlatego, że wszystkie odpowiedzi są pierwszymi czynnikami, długość jest równa 2?
— Pan Xcoder,
@MrXcoder Tak, dokładnie
— Business Cat
4 z nich są moje BTW> _>
— Mr. Xcoder
4 to także pierwszy semiprime. Straszny!
— Neil,
2

Java 8, 69 61 bajtów

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

-8 bajtów dzięki @Nevay .

Wypróbuj tutaj.

— Kevin Cruijssen
źródło
1
Możesz usunąć instrukcję else (która może być else++r;), aby zaoszczędzić 8 bajtów n->{int r=1,c=2;for(;r++<n;)for(;n%r<1;n/=r)c--;return c==0;}.
— Nevay,
1

C #, 112 bajtów

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

Po zastosowaniu formatowania:

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

I jako program testowy:

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

Który ma wynik:

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
źródło
1

Siatkówka , 45 bajtów

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

Wypróbuj online! Link zawiera przypadki testowe. Wyjaśnienie:

.+
$*

Konwertuj na unary.

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

Spróbuj znaleźć dwa czynniki.

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

Upewnij się, że oba czynniki są najważniejsze.

;

Upewnij się, że znaleziono dwa czynniki.

— Neil
źródło
1

Python 2, 90 bajtów

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

fprzyjmuje liczbę całkowitą nwiększą lub równą 1, zwraca wartość logiczną.

Wypróbuj online!

Przypadki testowe:

>>> 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
źródło
1

J , 6 bajtów

5 bajtów będzie działać jednorazowo:

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

Wydaje mi się, że potrzebuję sześciu, kiedy zdefiniuję funkcję:

   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
— Duńczyk
źródło
1

Japt , 6 5 bajtów

k ʥ2

Przetestuj online

Wyjaśnienie

Robi to prawie tak samo jak większość innych odpowiedzi: kpobiera tablicę czynników pierwszych, Êpobiera jej długość i ¥sprawdza równość z 2.

— Kudłaty
źródło
÷k o)jdziała również, niestety ma tę samą długość :-(
— ETHproductions
0

Perl 6 , 43 bajtów

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

Wypróbuj online!

fjest najmniejszym współczynnikiem większym niż 1 argument wejściowy $_lub Niljeśli $_wynosi 1. Zwracana wartość funkcji jest prawdziwa, jeśli fjest prawdziwa (tzn. nie Nil) ORAZ argument wejściowy podzielony przez współczynnik jest liczbą pierwszą.

Jeśli $_sama liczba pierwsza fjest równa , to będzie równa $_i $_ / fwynosi 1, co nie jest liczbą pierwszą, więc formuła również działa w tym przypadku.

— Sean
źródło
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.