เกือบจะเป็นนายก?

Aug 26 2020

แซนด์บ็อกซ์

ความหมาย:เป็นจำนวนเต็มบวกnเป็นเกือบสำคัญถ้ามันสามารถเขียนในรูปแบบn=p^kที่pเป็นนายกรัฐมนตรีและkยังเป็นจำนวนเต็มบวก กล่าวอีกนัยหนึ่งการแยกตัวประกอบเฉพาะของnมีเพียงจำนวนเดียวกัน

อินพุต:จำนวนเต็มบวก2<=n<=2^31-1

เอาท์พุท:ค่าที่แท้จริงถ้าnเป็นค่าเกือบเป็นค่าเฉพาะและค่าเท็จถ้าไม่ใช่

กรณีทดสอบความจริง:

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

กรุณาอย่าใช้ช่องโหว่มาตรฐาน นี่คือโค้ดกอล์ฟดังนั้นคำตอบที่สั้นที่สุดในหน่วยไบต์จึงชนะ!

คำตอบ

45 Sisyphus Aug 26 2020 at 10:08

Sagemath 2 ไบต์

GF

ขาออกผ่านทางข้อยกเว้น

ลองออนไลน์!


Sagemath ในตัว\$\text{GF}\$สร้างฟิลด์คำสั่งGalois \$n\$. อย่างไรก็ตามโปรดจำไว้ว่า\$\mathbb{F}_n\$เป็นเพียงข้อมูลถ้า\$n = p^k\$ที่ไหน\$p\$เป็นนายกและ\$k\$จำนวนเต็มบวก ดังนั้นฟังก์ชันจะแสดงข้อยกเว้นในกรณีที่อินพุตไม่ใช่กำลังหลักเท่านั้น

15 xnor Aug 26 2020 at 11:43

Python 2 , 42 ไบต์

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

ลองออนไลน์!

เนื่องจาก Python ไม่มีในตัวสำหรับ primes เราจึงทำการตรวจสอบการหาร

เราพบว่าไพรม์ที่เล็กที่สุดpซึ่งเป็นตัวประกอบของการnนับp=2,3,4,...จนกระทั่งnหารด้วยpนั่นn%pคือศูนย์ มีเราจะตรวจสอบว่านี้pเป็นเพียงปัจจัยที่สำคัญโดยการตรวจสอบว่ามีการใช้พลังงานสูงของการหารด้วยp nสำหรับสิ่งนี้p**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)

ลองออนไลน์!

13 RobinRyder Aug 26 2020 at 15:54

ภาษาการเขียนโปรแกรมของเช็คสเปียร์ 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จนAjaxเป็นตัวหารของPage; เรียกค่าสุดท้ายpสิ่งนี้ให้ตัวหารที่เล็กที่สุดPageซึ่งรับประกันได้ว่าเป็นจำนวนเฉพาะ
  • ฉาก X: Cube Ajaxจนกว่าคุณจะจบลงด้วยอำนาจของpการพูดซึ่งมากกว่าp^k nจากนั้นnจะnหารiff เกือบไพร์p^kม
11 LuisMendo Aug 26 2020 at 07:48

MATL , 4 ไบต์

Yf&=
  • สำหรับเกือบเฉพาะการส่งออกเป็นเมทริกซ์ที่มีเพียง1s ซึ่งเป็นtruthy
  • มิฉะนั้นออกเป็นเมทริกซ์ที่มีหลาย1s และอย่างน้อยหนึ่ง0ซึ่งเป็นfalsy

ลองออนไลน์! หรือตรวจสอบกรณีการทดสอบทั้งหมดรวมถึงการทดสอบความจริง / ความเท็จ

มันทำงานอย่างไร

     % Implicit input
Yf   % Prime factors. Gives a vector with the possibly repeated prime factors
&=   % Matrix of all pair-wise equality comparisons
     % Implicit output
9 RobinRyder Aug 26 2020 at 12:19

R , 36 32 29 ไบต์

-3 ไบต์โดยการส่งออกเวกเตอร์ของบูลีนโดยไม่ต้องแยกองค์ประกอบแรก

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

ลองออนไลน์!

แสดงเวกเตอร์ของบูลีน ใน R, เวกเตอร์ของ booleans เป็น truthy IFF TRUEองค์ประกอบแรกคือ

ขั้นแรกให้หาตัวหารที่เล็กที่สุดpของn. เราสามารถทำได้โดยการตรวจสอบจำนวนเต็มทั้งหมด (ไม่ใช่เฉพาะพรี) เนื่องจากตัวหารที่เล็กที่สุดของจำนวนเต็ม (นอกเหนือจาก 1) จะเป็นจำนวนเฉพาะเสมอ นี่ให้aเป็นจำนวนเต็มทั้งหมดระหว่าง2และnแล้วp=a[!n%%a][1]เป็นองค์ประกอบแรกของซึ่งแบ่งan

จากนั้นnเป็น IFF เกือบนายกแบ่งnp^n

สิ่งนี้ล้มเหลวสำหรับอินพุตที่มีขนาดใหญ่ปานกลางดังนั้นนี่คือเวอร์ชันก่อนหน้าซึ่งใช้ได้กับอินพุตที่ใหญ่ที่สุด:

R , 36 33 ไบต์

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

ลองออนไลน์!

คำนวณลอการิทึมของnin base p: นี่คือจำนวนเต็ม iff nเกือบเป็นไพรม์

สิ่งนี้จะล้มเหลวเนื่องจากความไม่ถูกต้องของจุดลอยตัวสำหรับอินพุตขนาดใหญ่ (แต่ห่างไกลจากทั้งหมด) โดยเฉพาะอย่างยิ่งสำหรับกรณีทดสอบเดียว: \$4913=17^3\$.

8 att Aug 26 2020 at 09:04

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
}
7 J42161217 Aug 26 2020 at 07:46

ภาษา Wolfram (Mathematica) , 11 ไบต์

PrimePowerQ

ลองออนไลน์!

@Sisyphus บันทึก 1 ไบต์

6 Sisyphus Aug 26 2020 at 08:17

05AB1E , 2 ไบต์

ÒË

ลองออนไลน์!

แสดงความคิดเห็น:

Ò   -- Are all the primes in the prime decomposition
 Ë  -- Equal?
6 Jonah Aug 26 2020 at 11:03

J , 9 8 ไบต์

1=#@=@q:

ลองออนไลน์!

-1 ไบต์ขอบคุณ xash

ทดสอบว่าการจำแนกตัวเอง =ของปัจจัยเฉพาะq:มีความยาว#เท่ากับหนึ่งหรือไม่1=

5 Razetime Aug 26 2020 at 11:32

APL (Dyalog Classic) , 33 31 26 ไบต์

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

-5 ไบต์จากคำแนะนำของ Kevin Cruijssen

คำเตือน:มากช้ามากสำหรับตัวเลขที่มากขึ้น

คำอธิบาย

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

ลองออนไลน์!

5 ManishKundu Aug 26 2020 at 10:32

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
5 bb94 Aug 26 2020 at 17:51

Setanta , 61 59 ไบต์

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

ลองดูที่นี่

หมายเหตุ:

  • คีย์เวิร์ดที่ถูกต้องคือgníomhแต่ Setanta อนุญาตให้สะกดได้โดยไม่ต้องเน้นเสียงดังนั้นฉันจึงต้องกำจัดไบต์ออกไป
3 xnor Aug 26 2020 at 15:16

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]

ลองออนไลน์!

3 Arnauld Aug 26 2020 at 13:43

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\$coprime กับ\$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

ลองออนไลน์!

3 Neil Aug 26 2020 at 17:11

Retina 0.8.2 , 50 ไบต์

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

ลองออนไลน์! ลิงก์มีกรณีทดสอบที่เร็วกว่า ขึ้นอยู่กับคำตอบ @ Deadcode เพื่อสตริงการแข่งขันมีความยาวเป็นอำนาจที่สี่ คำอธิบาย:

.+
$*

แปลงอินพุตเป็นยูนารี

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

เริ่มต้นโดยการจับคู่ปัจจัยที่มีขนาดเล็กที่สุด\ $ P \ $ของ\ $ n \ $ ( \ $ p \ $จำเป็นต้องเป็นไพรม์แน่นอน)

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

ในขณะที่\ $ p | \ frac {p n ^ i} \ $ค้นหา\ $ \ frac {p n ^ i} \ $ 's ปัจจัยที่เหมาะสมที่ใหญ่ที่สุดซึ่งจำเป็นต้อง\ $ \ frac {p n ^ {i + 1}} \ $

\4

การแยกตัวประกอบยังจับ\ $ (p - 1) \ frac n {p ^ {i + 1}} \ $ซึ่งหักออกจาก\ $ \ frac n {p ^ i} \ $ออกจาก\ $ \ frac n { p ^ {i + 1}} \ $สำหรับการผ่านลูปต่อไป

(...)+1$

ทำซ้ำการหารโดย\$ p \$กี่ครั้งก็ได้จากนั้นตรวจสอบว่า\$ \frac n { p^k } = 1 \$.

3 Noname Aug 26 2020 at 08:36

ไอโอ 48 ไบต์

พอร์ตของคำตอบ R ของ @ RobinRyder

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?
)
3 Noname Aug 26 2020 at 19:24

แอสเซมบลี (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

ลองออนไลน์!

3 xash Aug 26 2020 at 21:16

Brachylog 2 ไบต์

ปัจจัยสำคัญทั้งหมดเท่ากันหรือไม่?

ḋ=

ลองออนไลน์!

2 RosieF Aug 26 2020 at 12:44

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 ]อัตราผลตอบแทนถัวรายการ

ลองออนไลน์!

2 KevinCruijssen Aug 26 2020 at 14:50

MathGolf 10 ไบต์

╒g¶mÉk╒#─╧

ท่าเรือ@Razetime 's APL (Dyalog คลาสสิก) คำตอบเพื่อให้แน่ใจว่าจะ upvote เขาเช่นกัน!

ลองออนไลน์

คำอธิบาย:

╒           # 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)
2 GalenIvanov Aug 26 2020 at 15:24

แฟกเตอร์ 35 ไบต์

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

ลองออนไลน์!

2 Shaggy Aug 26 2020 at 15:41

Japt , 6 ไบต์

ฉันรู้สึกว่านี่ควรจะสั้นกว่านี้ 1 หรือ 2 ไบต์ ...

k ä¶ ×

ลองใช้ - รวมถึงกรณีทดสอบทั้งหมด

2 KevinCruijssen Aug 26 2020 at 16:28

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

หากเราได้รับอนุญาตให้เพิกเฉยต่อความไม่ถูกต้องของทศนิยมพอร์ตของคำตอบ Rของ@ RobinRyderจะเป็น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;}

ลองออนไลน์

2 cairdcoinheringaahing Aug 26 2020 at 17:06

เยลลี่ 3 ไบต์

ÆfE

ลองออนไลน์!

1 Mintable Aug 26 2020 at 16:21

Burlesque 6 ไบต์

rifCsm

ลองออนไลน์!

คำอธิบาย:

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