거의 프라임인가요?

Question

모래 상자

정의 : 양의 정수 n입니다 거의 프라임 이 형태로 기록 될 수 있다면, 소수이며, 또한 양의 정수이다. 즉,의 소인수 분해 에는 동일한 수만 포함됩니다.n=p^kpkn

입력 : 양의 정수2<=n<=2^31-1

출력 : 진실한 값, if nis almost-prime , 그렇지 않으면 거짓 값.

진정한 테스트 케이스 :

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

거짓 테스트 케이스

6
12
36
54
1938
5814
175560
9999999
17294403

표준 허점을 사용하지 마십시오. 이것은 코드 골프 이므로 바이트 단위의 가장 짧은 답변이 이깁니다!

Answer 1

Sagemath , 2 바이트

GF

예외 를 통해 출력합니다 .

온라인으로 시도하십시오!

---

Sagemath 내장 \$\text{GF}\$Galois Field of order \를 생성합니다.$n\$. 그러나 \$\mathbb{F}_n\$\ 인 경우에만 필드입니다.$n = p^k\$여기서 \$p\$소수이고 \$k\$양의 정수. 따라서 함수는 입력이 주력이 아닌 경우에만 예외를 발생시킵니다.

Answer 2

Python 2 , 42 바이트

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

온라인으로 시도하십시오!

파이썬에는 소수에 대한 내장 기능이 없기 때문에 분할 가능성을 확인합니다.

우리 는으로 나눌 수 있을 때까지 세어 p계수가 n되는 가장 작은 소수 , 즉 0을 찾습니다 . 여기에서 의 높은 거듭 제곱을 로 나눌 수 있는지 확인하여 이것이 유일한 소인수인지 확인합니다 . 이를 위해서는 충분합니다.p=2,3,4,...npn%pppnp**n

프로그램으로서 :

43 바이트

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

온라인으로 시도하십시오!

허용되는 경우 종료 코드로 더 짧을 수 있습니다.

46 바이트

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

온라인으로 시도하십시오!

Answer 3

셰익스피어 프로그래밍 언어 , 329 바이트

,.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

온라인으로 시도하십시오!

0입력이 거의 소수이면 출력 하고 그렇지 않으면 양의 정수입니다. 이것이 허용 가능한 출력인지 확실하지 않습니다. 변경하면 몇 바이트가 소요됩니다.

설명:

• 장면 I : Page입력을받습니다 (라고 부릅니다 n). 초기화 Ajax = 1.
• 장면 V : 의 제수가 Ajax될 때까지 증가 ; 최종 값을 호출합니다. 이것은 소수가 보장되는 의 최소 ​​제수를 제공합니다 .AjaxPagepPage
• 장면 X : 큐브는 Ajax당신의 힘을 끝낼 때까지 p, 말 p^k보다 더 크다 n. 그런 다음 n거의 프라임 iff n나누기 p^k입니다.

Answer 4

MATL , 4 바이트

Yf&=

• 거의 프라임의 경우 출력은 1s 만 포함하는 행렬 이며, 이는 truthy 입니다.
• 그렇지 않으면 출력은 여러 개의를 포함하는 행렬 1과 적어도 하나 0는 거짓 입니다.

온라인으로 시도하십시오! 또는 진실성 / 허위 테스트를 포함한 모든 테스트 사례를 확인합니다 .

작동 원리

     % 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 바이트

첫 번째 요소를 추출하지 않고 부울 벡터를 출력하여 -3 바이트

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

온라인으로 시도하십시오!

부울 벡터를 출력합니다. R에서 부울 벡터는 첫 번째 요소가이면 진실입니다 TRUE.

먼저의 최소 제수 p를 찾습니다 n. 정수의 최소 제수 (1을 제외하고)는 항상 소수이기 때문에 모든 정수 (소수뿐만 아니라)를 확인하여이를 수행 할 수 있습니다. 여기서하자 a사이의 모든 정수이어야 2하고 n, 다음 p=a[!n%%a][1]의 첫 번째 요소 인 a분할 n.

그런 다음 n거의 프라임 iff n나누기 p^n입니다.

이것은 적당히 큰 입력에 대해 실패하므로 다음은 대부분의 큰 입력에 대해 작동하는 이전 버전입니다.

R , 36 33 바이트

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

온라인으로 시도하십시오!

n밑수 의 로그를 계산합니다 p. 이것은 정수 n입니다.

이는 하나의 테스트 케이스를 위해, 특히, (그러나 지금까지 모든에서) 확실히 큰 틱 입력을 소수점 부정확성 부동에 실패합니다 \$4913=17^3\$.

Answer 6

C (gcc) , 43 바이트

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

온라인으로 시도하십시오!

거의 프라임 p이면 반환 n하고 1그렇지 않으면 반환합니다.

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 언어 (Mathematica) , 11 바이트

PrimePowerQ

온라인으로 시도하십시오!

@Sisyphus가 1 바이트 저장

Answer 8

05AB1E , 2 바이트

ÒË

온라인으로 시도하십시오!

댓글 :

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

Answer 9

J , ⁹ 8 바이트

1=#@=@q:

온라인으로 시도하십시오!

-xash 덕분에 1 바이트

소인수 의자가 분류 길이 가 1 인지 테스트합니다.=q:#1=

Answer 10

APL (Dyalog Classic) , 33 31 26 바이트

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

Kevin Cruijssen의 제안에서 -5 바이트.

경고 : 큰 숫자의 경우 매우 느립니다.

설명

{⍵∊∊(((⊢~∘.×⍨)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)?

온라인으로 시도하십시오!

Answer 11

Pyth , 5 바이트

!t{PQ

온라인으로 시도하십시오!

설명:

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 바이트

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

여기에서 시도

메모:

• 적절한 키워드는 gníomh이지만 Setanta는 악센트없이 철자를 허용하므로 한 바이트를 줄였습니다.

Answer 13

Haskell , 36 바이트

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

온라인으로 시도하십시오!

36 바이트

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

온라인으로 시도하십시오!

39 바이트

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

온라인으로 시도하십시오!

39 바이트

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

온라인으로 시도하십시오!

40 바이트

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

온라인으로 시도하십시오!

Answer 14

JavaScript (ES6), 43 바이트

BigInts없이

부울 값을 반환합니다.

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

온라인으로 시도하십시오!

가장 작은 제수를 먼저 찾는 재귀 함수 \$k>1\$의 \$n\$그런 다음 \$-n\$작성자 : \$k\$더 이상 정수가 아닐 때까지. (우리가 \ 의 부호를 반전시키는 유일한 이유$n\$때 \$k\$ 알고리즘의 두 단계를 구별하는 것입니다.)

만약 \$n\$거의 프라임, 최종 결과는 \$-\dfrac{1}{k}>-1\$. 그래서 우리는 \$\lceil n\rceil=0\$.

만약 \$n\$거의 프라임이 아니라 일부 \$q>k\$코 프라임 \$k\$그런 \$n=q\times k^{m}\$. 이 경우 최종 결과는 \$-\dfrac{q}{k}<-1\$. 그래서 우리는 \$\lceil n\rceil<0\$.

---

JavaScript (ES11), 33 바이트

BigInts로

BigInts에서는 @xnor의 접근 방식을 사용하는 것이 아마도 가장 짧은 방법 일 것입니다.

부울 값을 반환합니다.

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

온라인으로 시도하십시오!

Answer 15

Retina 0.8.2 , 50 바이트

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

온라인으로 시도하십시오! 링크에는 더 빠른 테스트 케이스가 포함됩니다. 길이가 4 제곱 인 문자열 일치에 대한 @Deadcode의 답변을 기반으로 합니다. 설명:

.+
$*

입력을 단항으로 변환합니다.

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

\ $ n \ $ 의 가장 작은 요소 \ $ p \ $ 를 매칭하여 시작합니다 . (물론 \ $ p \ $ 는 반드시 소수입니다.)

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

반면 | \ $ p를 \ frac n {p ^ i} \ $ , \ $ \ frac n {p ^ i} \ $ 의 가장 큰 적절한 인수를 찾습니다. 반드시 \ $ \ frac n {p ^ {i + 1}} \ $ 입니다.

\4

개에도 인수 분해 캡처 \ $ (p - 1) \ FRAC N {P ^ {I + 1}} \ $ 로부터 감산되는, \ $ \ FRAC N {P ^ 난} \ $ 떠나는 \ $ \ FRAC N { p ^ {i + 1}} \ $ 는 루프를 통과하는 다음 패스입니다.

(...)+1$

\로 나누기 반복$ p \$가능한 한 여러 번 확인한 다음 \$ \frac n { p^k } = 1 \$.

Answer 16

Io , 48 바이트

@RobinRyder의 R 답변 포트.

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

온라인으로 시도하십시오!

설명

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

어셈블리 (MIPS, SPIM) , 238 바이트, 6 * 23 = 138 어셈블리 바이트

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

온라인으로 시도하십시오!

Answer 18

Brachylog , 2 바이트

모든 소인수가 같습니까?

ḋ=

온라인으로 시도하십시오!

Answer 19

GAP 4.7, 31 바이트

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

이것은 람다입니다. 예를 들어,

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

목록을 생성합니다 [ 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 ].

온라인으로 시도하십시오!

Answer 20

MathGolf , 10 바이트

╒g¶mÉk╒#─╧

@Razetime 의 APL (Dyalog Classic) 답변의 포트이므로 그를 찬성 해야합니다!

온라인으로 시도하십시오.

설명:

╒           # 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

인수 , 35 바이트

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

온라인으로 시도하십시오!

Answer 22

Japt , 6 바이트

나는 이것이 1 또는 2 바이트 더 짧아야한다고 생각합니다 ...

k ä¶ ×

사용해보기 -모든 테스트 케이스 포함

Answer 23

Java, 69 (또는 64?) 바이트

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

온라인으로 시도하십시오.

설명:

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

---

우리는 소수점 부정확성 부동 무시하도록 허용 될 경우의 포트 RobinRyder의 R의 대답은 @ 것 64 바이트 대신 :

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

온라인으로 시도하십시오.

설명:

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

그러나 불행하게도이 방법은 테스트 케이스 실패 4913가 될 것 2.9999999999999996대신에 3.0(다른 모든 테스트 케이스에 대한 성공) 포인트 부정확 부동 때문.
잠재적 수정 사항은 71 바이트입니다 .

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

온라인으로 시도하십시오.

Answer 24

젤리 , 3 바이트

ÆfE

온라인으로 시도하십시오!

Answer 25

Burlesque , 6 바이트

rifCsm

온라인으로 시도하십시오!

설명:

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