เกือบจะเป็นนายก?
แซนด์บ็อกซ์
ความหมาย:เป็นจำนวนเต็มบวก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
กรุณาอย่าใช้ช่องโหว่มาตรฐาน นี่คือโค้ดกอล์ฟดังนั้นคำตอบที่สั้นที่สุดในหน่วยไบต์จึงชนะ!
คำตอบ
Sagemath 2 ไบต์
GF
ขาออกผ่านทางข้อยกเว้น
ลองออนไลน์!
Sagemath ในตัว\$\text{GF}\$สร้างฟิลด์คำสั่งGalois \$n\$. อย่างไรก็ตามโปรดจำไว้ว่า\$\mathbb{F}_n\$เป็นเพียงข้อมูลถ้า\$n = p^k\$ที่ไหน\$p\$เป็นนายกและ\$k\$จำนวนเต็มบวก ดังนั้นฟังก์ชันจะแสดงข้อยกเว้นในกรณีที่อินพุตไม่ใช่กำลังหลักเท่านั้น
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)
ลองออนไลน์!
ภาษาการเขียนโปรแกรมของเช็คสเปียร์ 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^knจากนั้นnจะnหารiff เกือบไพร์p^kม
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
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\$.
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
}
ภาษา Wolfram (Mathematica) , 11 ไบต์
PrimePowerQ
ลองออนไลน์!
@Sisyphus บันทึก 1 ไบต์
05AB1E , 2 ไบต์
ÒË
ลองออนไลน์!
แสดงความคิดเห็น:
Ò -- Are all the primes in the prime decomposition
Ë -- Equal?
J , 9 8 ไบต์
1=#@=@q:
ลองออนไลน์!
-1 ไบต์ขอบคุณ xash
ทดสอบว่าการจำแนกตัวเอง =ของปัจจัยเฉพาะq:มีความยาว#เท่ากับหนึ่งหรือไม่1=
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)?
ลองออนไลน์!
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
Setanta , 61 59 ไบต์
gniomh(n){p:=2nuair-a n%p p+=1nuair-a n>1 n/=p toradh n==1}
ลองดูที่นี่
หมายเหตุ:
- คีย์เวิร์ดที่ถูกต้องคือ
gníomhแต่ Setanta อนุญาตให้สะกดได้โดยไม่ต้องเน้นเสียงดังนั้นฉันจึงต้องกำจัดไบต์ออกไป
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]
ลองออนไลน์!
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
ลองออนไลน์!
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 \$.
ไอโอ 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?
)
แอสเซมบลี (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
ลองออนไลน์!
Brachylog 2 ไบต์
ปัจจัยสำคัญทั้งหมดเท่ากันหรือไม่?
ḋ=
ลองออนไลน์!
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 ]อัตราผลตอบแทนถัวรายการ
ลองออนไลน์!
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)
แฟกเตอร์ 35 ไบต์
: f ( n -- ? ) factors all-equal? ;
ลองออนไลน์!
Japt , 6 ไบต์
ฉันรู้สึกว่านี่ควรจะสั้นกว่านี้ 1 หรือ 2 ไบต์ ...
k ä¶ ×
ลองใช้ - รวมถึงกรณีทดสอบทั้งหมด
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;}
ลองออนไลน์
เยลลี่ 3 ไบต์
ÆfE
ลองออนไลน์!
Burlesque 6 ไบต์
rifCsm
ลองออนไลน์!
คำอธิบาย:
ri # Read integer from input
fC # Find its prime factorisation
sm # Are all values the same?