Neredeyse asal mı?

Question

Kum havuzu

Tanım: Pozitif bir tam sayı nolduğu neredeyse asal o şeklinde yazılabilir eğer, bir asal olduğunu ve aynı zamanda bir pozitif tam olduğunu. Başka bir deyişle, asal çarpanlara ayırma yalnızca aynı sayıyı içerir.n=p^kpkn

Girdi: Pozitif bir tam sayı2<=n<=2^31-1

Çıktı: Bir truthy değeri, eğer nolduğunu neredeyse asal ve falsy değer, değilse.

Doğruluk Testi Durumları:

2
3
4
8
9
16
25
27
32
49
64
81
1331
2401
4913
6859
279841
531441
1173481
7890481
40353607
7528289

Sahte Test Durumları

6
12
36
54
1938
5814
175560
9999999
17294403

Lütfen standart boşluklar kullanmayın. Bu kod golfüdür, bu yüzden bayt cinsinden en kısa cevap kazanır!

Answer 1

Sagemath , 2 bayt

GF

İstisna yoluyla çıktılar .

Çevrimiçi deneyin!

---

Sagemath yerleşik \$\text{GF}\$bir Galois düzen alanı yaratır \$n\$. Ancak şunu unutmayın \$\mathbb{F}_n\$eğer \$n = p^k\$nerede \$p\$asal ve \$k\$pozitif bir tam sayı. Böylece işlev, ancak ve ancak girdisi bir asal güç değilse bir istisna atar.

Answer 2

Python 2 , 42 bayt

f=lambda n,p=2:n%p and f(n,p+1)or p**n%n<1

Çevrimiçi deneyin!

Python, asal sayılar için yerleşik bir yapıya sahip olmadığından, bölünebilirliği kontrol etmekle yetiniyoruz.

Biz en küçük asal bulmak pbir faktör olduğunu nyukarı sayarak p=2,3,4,...kadar nbölünebilen polup, n%psıfırdır. Orada, pyüksek bir gücün pile bölünebilir olduğunu kontrol ederek bunun tek asal faktör olduğunu kontrol ediyoruz n. Bunun için p**nyeterli.

Bir program olarak:

43 bayt

n=input()
p=2
while n%p:p+=1
print p**n%n<1

Çevrimiçi deneyin!

Bu, izin veriliyorsa çıkış kodlarıyla daha kısa olabilir.

46 bayt

lambda n:all(n%p for p in range(2,n)if p**n%n)

Çevrimiçi deneyin!

Answer 3

Shakespeare Programlama Dili , 329 bayt

,.Ajax,.Page,.Act I:.Scene I:.[Enter Ajax and Page]
Ajax:Listen tothy.
Page:You cat.
Scene V:.
Page:You is the sum ofYou a cat.
 Is the remainder of the quotient betweenI you nicer zero?If soLet usScene V.
Scene X:.
Page:You is the cube ofYou.Is you worse I?If soLet usScene X.
 You is the remainder of the quotient betweenYou I.Open heart

Çevrimiçi deneyin!

0Girdi neredeyse asal, aksi halde pozitif bir tam sayı ise çıktılar . Bunun kabul edilebilir bir çıktı olduğundan emin değilim; bunu değiştirmek birkaç bayta mal olur.

Açıklama:

• Sahne I: Pagegirişi alır (bunu arayın n). Başlatın Ajax = 1.
• Sahne V: Bir bölen Ajaxolana kadar Ajaxartırın Page; son değeri çağır pBu, Pageasal olması garantili olan en küçük bölenini verir .
• Sahne X: AjaxBir güç elde edene kadar küp p, diyelim ki p^khangisi daha büyük n. Sonra nneredeyse asal nikiye bölünür p^k.

Answer 4

MATL , 4 bayt

Yf&=

• Neredeyse asal sayılar için çıktı yalnızca 1s içeren bir matristir ki bu doğrudur .
• Aksi takdirde çıktı, birkaç 1s ve en az bir tane içeren ve yanlış0 olan bir matristir .

Çevrimiçi deneyin! Veya doğruluk / yanlışlık testi dahil tüm test durumlarını doğrulayın .

Nasıl çalışır

     % Implicit input
Yf   % Prime factors. Gives a vector with the possibly repeated prime factors
&=   % Matrix of all pair-wise equality comparisons
     % Implicit output

Answer 5

R , 36 32 29 bayt

İlk öğeyi çıkarmadan bir boole vektörü çıkararak -3 bayt

!(a=2:(n=scan()))[!n%%a]^n%%n

Çevrimiçi deneyin!

Bir boole vektörü çıkarır. R'de, boolelerin bir vektörü, ilk eleman olduğu sürece doğrudur TRUE.

İlk olarak, en küçük böleni bulmak pait n. Bunu, tüm tam sayıları (yalnızca asal sayıları değil) kontrol ederek yapabiliriz, çünkü bir tamsayının en küçük bölen (1 dışında) her zaman bir asal sayıdır. Burada, ve aarasındaki tüm tamsayılar olsun , o zaman bölen ilk elemandır .2np=a[!n%%a][1]an

O zaman nneredeyse asal nikiye bölünür p^n.

Bu, orta büyüklükteki herhangi bir giriş için başarısız olur, bu nedenle, çoğu büyük giriş için çalışan önceki sürüm burada:

R , 36 33 bayt

!log(n<-scan(),(a=2:n)[!n%%a])%%1

Çevrimiçi deneyin!

Logaritmasını hesaplayın ntabanında p: Bu bir tamsayı IFF olduğu nasalımsı olduğunu.

Bunun nedeni bir test durumu için özellikle (ama hepsi değil) kesin olarak geniş imsi girişler noktası yanlışlığı yüzen için başarısız olur: \$4913=17^3\$.

Answer 6

C (gcc) , 43 bayt

f(n,i){for(i=1;n%++i;);n=i<n&&f(n/i)^i?:i;}

Çevrimiçi deneyin!

İade pdurumunda nneredeyse asal ve bir 1başka türlü.

f(n,i){
    for(i=1;n%++i;);    // identify i = the least prime factor of n
    n=i<n&&f(n/i)^i     // if n is neither prime nor almost-prime
      ?                 //  return 1
      :i;               // return i
}

Answer 7

Wolfram Dili (Mathematica) , 11 bayt

PrimePowerQ

Çevrimiçi deneyin!

@Sisyphus 1 bayt kaydetti

Answer 8

05AB1E , 2 bayt

ÒË

Çevrimiçi deneyin!

Yorum yaptı:

Ò   -- Are all the primes in the prime decomposition
 Ë  -- Equal?

Answer 9

J , ⁹ 8 bayt

1=#@=@q:

Çevrimiçi deneyin!

Xash sayesinde -1 bayt

Asal faktörlerin kendi sınıflandırmasının bire eşit uzunluğa sahip =olup olmadığını test ederq:#1=

Answer 10

APL (Dyalog Classic) , 33 31 26 bayt

{⍵∊∊(((⊢~∘.×⍨)1↓⍳)⍵)∘*¨⍳⍵}

Kevin Cruijssen'in önerisinden -5 bayt.

Uyarı: Daha büyük sayılar için çok çok yavaş.

Açıklama

{⍵∊∊(((⊢~∘.×⍨)1↓⍳)⍵)∘*¨⍳⍵} ⍵=n in all the following steps
                       ⍳⍵  range from 1 to n
                    ∘*¨    distribute power operator across left and right args
    (((⊢~∘.×⍨)1↓⍳)⍵)       list of primes till n
   ∊                       flatten the right arg(monadic ∊)
 ⍵∊                        is n present in the primes^(1..n)?

Çevrimiçi deneyin!

Answer 11

Pyth , 5 bayt

!t{PQ

Çevrimiçi deneyin!

Açıklama:

Q - Takes integer input
P - List of prime factors
{ - Remove duplicate elements
t - Removes first element
! - Would return True if remaining list is empty, otherwise False

Answer 12

Setanta , 61 59 bayt

gniomh(n){p:=2nuair-a n%p p+=1nuair-a n>1 n/=p toradh n==1}

Burada deneyin

Notlar:

• Doğru anahtar kelime şudur gníomh, ancak Setanta aksanlar olmadan yazılmasına izin verir, bu yüzden bunu bir baytı kesip atmak için yaptım.

Answer 13

Haskell , 36 bayt

f n=mod(until((<1).mod n)(+1)2^n)n<1

Çevrimiçi deneyin!

36 bayt

f n=and[mod(gcd d n^n)n<2|d<-[1..n]]

Çevrimiçi deneyin!

39 bayt

f n=all((`elem`[1,n]).gcd n.(^n))[2..n]

Çevrimiçi deneyin!

39 bayt

f n=mod n(n-sum[1|1<-gcd n<$>[1..n]])<1

Çevrimiçi deneyin!

40 bayt

f n=and[mod(p^n)n<1|p<-[2..n],mod n p<1]

Çevrimiçi deneyin!

Answer 14

JavaScript (ES6), 43 bayt

BigInts olmadan

Bir Boolean değeri döndürür.

f=(n,k=1)=>n%1?!~~n:f(n<0?n/k:n%++k?n:-n,k)

Çevrimiçi deneyin!

İlk olarak en küçük bölenleri arayan özyinelemeli bir işlev \$k>1\$arasında \$n\$ve sonra böler \$-n\$tarafından \$k\$artık tam sayı olmayana kadar. ( \ İşaretini ters çevirmemizin tek nedeni$n\$ne zaman \$k\$ Algoritmanın iki adımı arasında ayrım yapmaktır.)

Eğer \$n\$neredeyse asal, nihai sonuç \$-\dfrac{1}{k}>-1\$. Böylece \ ile sonuçlanırız$\lceil n\rceil=0\$.

Eğer \$n\$neredeyse asal değil, biraz var \$q>k\$ile coprime \$k\$öyle ki \$n=q\times k^{m}\$. Bu durumda, nihai sonuç \$-\dfrac{q}{k}<-1\$. Böylece \ ile sonuçlanırız$\lceil n\rceil<0\$.

---

JavaScript (ES11), 33 bayt

BigInts ile

BigInts ile @ xnor'un yaklaşımını kullanmak muhtemelen en kısa yol.

Bir Boolean değeri döndürür.

f=(n,k=1n)=>n%++k?f(n,k):k**n%n<1

Çevrimiçi deneyin!

Answer 15

Retina 0.8.2 , 50 bayt

.+
$* ^(?=(11+?)\1*$)((?=\1+$)(?=(1+)(\3+)$)\4)+1$

Çevrimiçi deneyin! Link, daha hızlı test senaryoları içerir. @ Deadcode'un uzunluğu dördüncü kuvvet olan Eşleştirme dizelerine verdiği cevaba dayanmaktadır . Açıklama:

.+
$*

Girişi tekliye dönüştürün.

^(?=(11+?)\1*$)

En küçük faktör olan \ $ p \ $ / \ $ n \ $ ile eşleştirerek başlayın . ( Elbette \ $ p \ $ zorunlu olarak asaldır.)

(?=\1+$)(?=(1+)(\3+)$)

İken | \ $ s \ frac n {p ^ i} \ $ , \ $ \ frac n {p ^ i} \ $ 'nın en büyük uygun çarpanını bulun , bu zorunlu olarak \ $ \ frac n {p ^ {i + 1}} \ $ ' dır .

\4

Ayrıca factorisation yakalar \ $ (p - 1) \ frac n {p ^ {i + 1}} \ $ çıkarılır olan, \ $ \ frac n {p ^ i} \ $ , ayrılan \ $ \ frac n { p ^ {i + 1}} \ $ döngüden sonraki geçiş için.

(...)+1$

Bölmeyi \ ile tekrarlayın$ p \$mümkün olduğunca çok kez, ardından kontrol edin \$ \frac n { p^k } = 1 \$.

Answer 16

Io , 48 bayt

Port of @ RobinRyder'ın R cevabı.

method(i,c :=2;while(i%c>0,c=c+1);i log(c)%1==0)

Çevrimiçi deneyin!

Açıklama

method(i,            // Take an input
    c := 2           // Set counter to 2
    while(i%c>0,     // While the input doesn't divide counter:
        c=c+1        //     Increment counter
    )
    i log(c)%1==0    // Is the decimal part of input log counter equal to 0?
)

Answer 17

Derleme (MIPS, SPIM) , 238 bayt, 6 * 23 = 138 birleştirilmiş bayt

main:li$v0,5 syscall move$t3,$v0 li$a0,0
li$t2,2 w:bgt$t2,$t3,d div$t3,$t2 mfhi$t0
bnez$t0,e add$a0,$a0,1 s:div$t3,$t2 mfhi$t0
bnez$t0,e div$t3,$t3,$t2
b s
e:add$t2,$t2,1
b w
d:move$t0,$a0
li$a0,0 bne$t0,1,p
add$a0,$a0,1
p:li$v0,1
syscall

Çevrimiçi deneyin!

Answer 18

Brachylog , 2 bayt

Tüm asal çarpanlar eşit mi?

ḋ=

Çevrimiçi deneyin!

Answer 19

GAP 4.7, 31 bayt

n->Length(Set(FactorsInt(n)))<2

Bu bir lambda. Örneğin, ifade

Filtered([2..81], n->Length(Set(FactorsInt(n)))<2 );

listeyi verir [ 2, 3, 4, 5, 7, 8, 9, 11, 13, 16, 17, 19, 23, 25, 27, 29, 31, 32, 37, 41, 43, 47, 49, 53, 59, 61, 64, 67, 71, 73, 79, 81 ].

Çevrimiçi deneyin!

Answer 20

MathGolf , 10 bayt

╒g¶mÉk╒#─╧

Port of @Razetime'ın APL (Dyalog Classic) cevabı , bu yüzden ona da olumlu oy verdiğinizden emin olun!

Çevrimiçi deneyin.

Açıklama:

╒           # Push a list in the range [1, (implicit) input-integer)
 g          # Filter it by:
  ¶         #  Check if it's a prime
   m        # Map each prime to,
    É       # using the following three operations:
     k╒     #  Push a list in the range [1, input-integer) again
       #    #  Take the current prime to the power of each value in this list
        ─   # After the map, flatten the list of lists
         ╧  # And check if this list contains the (implicit) input-integer
            # (after which the entire stack joined together is output implicitly)

Answer 21

Faktör , 35 bayt

: f ( n -- ? ) factors all-equal? ;

Çevrimiçi deneyin!

Answer 22

Japt , 6 bayt

Bunun 1 veya 2 bayt daha kısa olması gerektiğini düşünüyorum ...

k ä¶ ×

Deneyin - tüm test durumlarını içerir

Answer 23

Java, 69 (veya 64?) Bayt

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

Çevrimiçi deneyin.

Açıklama:

n->{                // Method with integer parameter and boolean return-type
  int c=0,          //  Counter-integer, starting at 0
  t=1;for(;t++<n;)  //  Loop `t` in the range (1,n]:
    if(n%t<1)       //   If the input is divisible by `t`:
      for(c++;      //    Increase the counter by 1
          n%t<1;)   //    Loop as long as the input is still divisible by `t`
        n/=t;       //     And divide `n` by `t` every iteration
  return c<2;}      //  Return whether the counter is 1

---

Kayan nokta yanlışlıklarını göz ardı etmemize izin verilirse, @ RobinRyder'ın R cevabının bir bağlantı noktası 64 bayt olacaktır :

n->{int m=1;for(;n%++m>0;);return Math.log(n)/Math.log(m)%1==0;}

Çevrimiçi deneyin.

Açıklama:

n->{               // Method with integer parameter and boolean return-type
  int m=1;         //  Minimum divisor integer `m`, starting at 1
  for(;n%++m>0;);  //  Increase `m` by 1 before every iteration with `++m`
                   //  And continue looping until the input is divisible by `m`
  return Math.log(n)/Math.log(m)
                   //  Calculate log_m(n)
         %1==0;}   //  And return whether it has no decimal values after the comma

Ancak maalesef bu yaklaşım , kayan nokta yanlışlıkları yerine 4913olacak olan test senaryosu için başarısız olur (diğer tüm test durumları için başarılıdır). Olası bir düzeltme 71 bayt olacaktır :2.99999999999999963.0

n->{int m=1;for(;n%++m>0;);return(Math.log(n)/Math.log(m)+1e9)%1<1e-8;}

Çevrimiçi deneyin.

Answer 24

Jöle , 3 bayt

ÆfE

Çevrimiçi deneyin!

Answer 25

Burlesque , 6 bayt

rifCsm

Çevrimiçi deneyin!

Açıklama:

ri      # Read integer from input
  fC    # Find its prime factorisation
    sm  # Are all values the same?