Daftar bilangan prima di bawah satu juta

56

Ini adalah pertanyaan golf kode pertama saya, dan sangat sederhana, jadi saya minta maaf sebelumnya jika saya mungkin telah melanggar pedoman komunitas.

Tugasnya adalah mencetak, dalam urutan menaik, semua bilangan prima kurang dari satu juta. Format output harus satu angka per baris output.

Tujuannya, seperti pada kebanyakan pengiriman kode golf, adalah untuk meminimalkan ukuran kode. Mengoptimalkan runtime juga merupakan bonus, tetapi merupakan tujuan sekunder.

Delan Azabani
sumber
12
Ini bukan duplikat yang tepat, tetapi pada dasarnya hanya pengujian primality, yang merupakan komponen dari sejumlah pertanyaan yang ada (misalnya codegolf.stackexchange.com/questions/113 , codegolf.stackexchange.com/questions/5087 , codegolf.stackexchange. com / pertanyaan / 1977 ). FWIW, salah satu pedoman yang tidak cukup diikuti (bahkan oleh orang-orang yang seharusnya tahu lebih baik) adalah dengan mengajukan terlebih dahulu pertanyaan di meta sandbox meta.codegolf.stackexchange.com/questions/423 untuk kritik dan diskusi tentang bagaimana bisa ditingkatkan sebelum orang mulai menjawabnya.
Peter Taylor
Ah, ya, saya khawatir pertanyaan ini terlalu mirip dengan kebanyakan pertanyaan terkait nomor prima yang sudah ada.
Delan Azabani
2
@ GlennRanders-Pehrson Karena 10^6bahkan lebih pendek;)
ɐɔıʇǝɥʇu 14s
1
Beberapa tahun yang lalu saya mengirimkan entri IOCCC yang mencetak bilangan prima dengan hanya 68 karakter dalam C - sayangnya itu berhenti kurang dari satu juta, tetapi mungkin menarik bagi beberapa orang: computronium.org/ioccc.html
Computronium
1
@ ɐɔıʇǝɥʇuʎs Bagaimana dengan 1e6:-D
Titus

Jawaban:

33

Mathematica , 17 24

Hanya untuk perbandingan:

Prime@Range@78498

Seperti disebutkan dalam komentar saya gagal memberikan satu prime per baris; koreksi:

Column@Prime@Range@78498
Tuan Penyihir
sumber
4
Prime~Array~78498juga 17 :)
chyanog
Akan menjadi sembilan byte di mthmca, jika itu akan dirilis.
Michael Stern
Itu melanggar kondisi satu prima per lini output. Awalan Print/@dan terminasi dengan ;untuk mencegah keluaran dari daftar panjang Nullperbaikan yang, dengan biaya 8 karakter tambahan.
celtschk
@celtschk Saya tidak tahu apakah saya melewatkan atau mengabaikannya lima tahun lalu.
Mr.Wizard
1
Yah, saya pasti merindukan itu dari lima tahun yang lalu :-)
celtschk
27

Python 3, 46 byte

k=P=1
while k<1e6:P%k and print(k);P*=k*k;k+=1

Pada saat loop mencapai pengujian k, iteratif menghitung faktor kuadrat P=(k-1)!^2. Jika kprima, maka itu tidak muncul dalam produk 1 * 2 * ... * (k-1), jadi itu bukan faktor P. Tapi, jika itu komposit, semua faktor utamanya lebih kecil dan begitu juga dalam produk. Kuadrat sebenarnya hanya diperlukan untuk berhenti k=4dari salah disebut prima.

Lebih kuat lagi, teorema Wilson menyatakan bahwa ketika kprima, P%ksama dengan 1. Meskipun kita hanya perlu bukan nol di sini, ini berguna secara umum yang P%kmerupakan variabel indikator untuk apakah kprime.

Tidak
sumber
23

C, 61 karakter

Hampir persis sama dengan yang ini (pertanyaannya juga hampir sama persis).

n=2;main(m){n<1e6&&main(m<2?printf("%d\n",n),n:n%m?m-1:n++);}
ugoren
sumber
Dapat SEG-FAULTsetelah mencetak881
manav mn
7
@Manav, mungkin Anda dikompilasi tanpa optimasi. Itu bergantung pada pengoptimal yang baik, yang akan menghapus rekursi.
ugoren
4
Ya menambahkan -O3untuk gccmenyelesaikan masalah !!
manav mn
Metode ini gila. Aku menyukainya.
Todd Lehman
2
Saya bisa membuat Anda sampai 57 byten=2;main(m){n<1e6&&main(m<2?printf("%d\n",n),n:m-++n%m);}
Albert Renshaw
22

MATLAB (16) (12)

Sayangnya, ini menghasilkan satu baris:

primes(1000000)

tapi itu diselesaikan dengan transpose matriks sederhana:

primes(1000000)'

dan saya dapat memotong beberapa karakter dengan menggunakan notasi eksponensial (seperti yang disarankan dalam komentar):

primes(1e6)'
MBraedley
sumber
5
Menggunakan 1e6bukannya 1000000membantu di sini juga.
orion
@orion Itu akan membuatnya menjadi 11 karakter
Axoren
@Axoren yang tidak termasuk 'di akhir
Stan Strum
20

Bash (37 karakter)

seq 2 1e6|factor|sed 's/.*: //g;/ /d'

(60 karakter)

seq 2 1000000|factor|sed -e 's/[0-9]*: //g' -e '/^.* .*$/ d'

di komputer saya (cpu 2,0 GHz, ram 2 GB) membutuhkan waktu 14 detik.

Saeedn
sumber
Ini dapat ditingkatkan ke: seq 2 1000000|factor|sed 's/[0-9]*: //g;/^.* .*$/ d'
Delan Azabani
ya kau benar. Saya menulis perintah sed saya bersih, bukan
golf
3
seq 1e6|factor|awk '$0=$2*!$3'sedikit lebih pendek.
Dennis
1
seq, faktor dan sed adalah program eksternal, ini mungkin juga di c pmana c adalah symlink ke cat dan p adalah file teks dengan bilangan prima hingga satu juta ... dapatkah Anda melakukannya dengan builtin shell?
technosaurus
7
@ technosaurus seqdan factorberada di coreutils, jadi itu sah. sedjuga cukup di mana-mana. coreutilsdapat diperlakukan seperti built-in. Bash tanpa coreutils seperti C ++ tanpa STL.
16

J, 21 karakter

1[\p:i.(_1 p:1000000)

yang dapat disingkat menjadi

1[\p:i.78498

jika Anda tahu berapa banyak bilangan prima ada di bawah 10.00000.

Gareth
sumber
2
Menggunakan item enfile ,.,, alih-alih 1 [\\ untuk menyimpan karakter. Lepaskan kurung yang tidak perlu, dan menggunakan notasi eksponensial: 1e6.
Omar
Datang dengan ini: ,.i.&.(p:^:_1)1e6Tidak lebih pendek (setelah menerapkan saran @ Umar) tapi saya menemukan penggunaan di bawah menarik.
kaoD
10

PowerShell, 47 44 byte

Sangat lambat, tapi yang terpendek yang bisa saya lakukan.

$p=2..1e6;$p|?{$n=$_;!($p-lt$_|?{!($n%$_)})}

PowerShell, 123 byte

Ini jauh lebih cepat; jauh dari optimal, tetapi kompromi yang baik antara efisiensi dan singkatnya.

 $p=2..1e6;$n=0
 while(1){$p=@($p[0..$n]|?{$_})+($p[($n+1)..($p.count-1)]|?{$_%$p[$n]});$n++;if($n-ge($p.count-1)){break}}
 $p
Berasal
sumber
9

Ruby 34

require'prime';p Prime.take 78498
Hauleth
sumber
9

Bash, 30 byte

Karena saeedn tidak akan bertindak atas saran saya - yang lebih pendek dan lebih cepat daripada pendekatannya - saya pikir saya akan memposting jawaban saya sendiri:

seq 1e6|factor|awk '$0=$2*!$3'

Bagaimana itu bekerja

seq 1e6

daftar semua bilangan bulat positif hingga 1.000.000.

factor

faktor mereka satu per satu. Untuk sepuluh pertama, hasilnya adalah sebagai berikut:

1:
2: 2
3: 3
4: 2 2
5: 5
6: 2 3
7: 7
8: 2 2 2
9: 3 3
10: 2 5

Akhirnya,

awk '$0=$2*!$3'

mengubah seluruh baris ( $0) ke produk dari bidang kedua (faktor prima pertama) dan negasi logis dari bidang ketiga ( 1jika merupakan satu faktor prima atau kurang, 0jika tidak).

Ini menggantikan garis yang sesuai dengan bilangan prima dengan angka itu sendiri dan semua garis lainnya dengan nol. Karena awk hanya mencetak nilai kebenaran, hanya bilangan prima yang akan dicetak.

Dennis
sumber
4
awk '$0=$2*!$3'sangat keren!
yeti
8

Ruby 50 41

require'mathn'
p (2..1e6).select &:prime?
Cristian Lupascu
sumber
2
Tidak perlu .to_a, karena Enumerable sudah termasuk select. Anda juga dapat menggunakan notasi steno untuk Simbol # to_proc untuk mempersingkat lebih lanjut: p (2..1e6).select &:prime?(1 bukan prime)
Ventero
@Ventero terima kasih banyak! Saya tidak tahu tentang simbol # to_proc. Saya harus lebih memperhatikan cara pintas yang ditawarkan Ruby.
Cristian Lupascu
2
Versi lebih pendek require'prime';p Prime.take 78498.
Hauleth
@ ŁukaszNiemier Hebat! Saya pikir itu sangat berbeda sehingga Anda dapat mempostingnya sebagai jawaban terpisah.
Cristian Lupascu
Penggunaan yang bagus dari 'country boy mathn' yang bagus
DoctorHeckle
8

Bash, 37

Akan bermain golf lebih banyak, jika aku bisa ...

Sebagian besar dari ini mencoba mem factor- parsing format output yang canggung.

seq 1e6|factor|grep -oP "(?<=: )\d+$"

Butuh 5,7 detik untuk menyelesaikannya di mesin saya.

(Kebetulan posting saya adalah yang pertama masuk pada halaman kedua jawaban, jadi tidak ada yang akan melihatnya ...)

Solusi lama

Ini lebih lama dan lebih lambat (butuh 10 detik).

seq 1e6|factor|egrep ':.\S+$'|grep -oE '\S+$'

sumber
2
Wow - Saya tidak pernah menemukan factorsebelumnya, tetapi ada di sana di coreutils!
Trauma Digital
1
Shave off one character: seq 1e6|factor|grep -oP "(?<=: )\d+$"with perl-grep lookbehind
Digital Trauma
@DigitalTrauma bagaimana cara kerjanya
1
-Pmemungkinkan regex gaya-perl. (?<=: )adalah tampilan positif di balik string ":". Pada dasarnya ini mengatakan bahwa ":" harus datang sebelum pertandingan apa \d+$, tetapi sebenarnya bukan bagian dari pertandingan, jadi -oopsi hanya memberi kita satu angka yang cocok setelah titik dua, yaitu hanya memberikan angka di mana hanya ada satu faktor, yaitu prima.
Digital Trauma
@DigitalTrauma menambahkan
8

Python 3.x: 66 karakter

for k in range(2,10**6):
 if all(k%f for f in range(2,k)):print(k)

Solusi yang lebih efisien: 87 karakter

Berdasarkan Saringan Eratosthenes.

p=[];z=range(2,10**6)
while z:f=z[0];p+=[f];z=[k for k in z if k%f]
for k in p:print(k)
dan04
sumber
1
Yang pertama salah mencetak 0dan 1. Anda dapat memperbaikinya dengan menggunakan range(2,10**6). Juga, saya pikir ifpernyataan itu harus berada di jalur yang terpisah dari luar foratau Anda mendapatkan kesalahan.
xnor
@ xnor: Memperbaikinya.
dan04
8

Haskell, 51

mapM print [n|n<-[2..10^6],all((>0).rem n)[2..n-1]]
pt2121
sumber
Anda dapat mengubah mapM_ke mapM, nilai pengembalian tidak akan dicetak, dan ini adalah Code Golf. ;)
Dogbert
mengapa ada spasi tambahan setelah cetak dan dalam (> 0)?
haskeller bangga
tangkapan bagus! terima kasih
pt2121
Anda dapat mengganti 999999 dengan 10 ^ 6. Dan perbarui jumlah byte Anda - 63 tidak mungkin benar.
user2845840
@ user2845840 ok terima kasih. ide bagus!
pt2121
8

APL, 15

p~,p∘.×p←1↓⍳1e6

Penerjemah saya mengalami masalah memori, tetapi itu bekerja secara teori.

TwiNight
sumber
Bagaimana? Bisakah Anda memberikan deskription?
Rasmus Damgaard Nielsen
Anda memerlukan di depan untuk membuat satu angka per baris, dan Anda tidak memerlukannya ,.
Adám
@RasmusDamgaardNielsen adalah bilangan bulat pertama. 1↓menjatuhkan yang pertama. p←ditugaskan ke hal. p∘.×pmembuat tabel perkalian. p~menghapus dari p apa pun yang ada di kanan. ( ,tidak diperlukan, itu mencungkil tabel ke dalam daftar.)
Adám
8

Perl, 49 byte

Ekspresi reguler kung fu :)

for(1..1E6){(1x$_)=~/^(11+?)\1+$/ or print"$_\n"}

Versi tidak disatukan:

for(1 .. 1_000_000) { 
    (1x$_) =~ /^(11+?)\1+$/ or print "$_\n";
}

Bahkan belum membuat kemajuan 10% saat saya mengetik posting ini!

Sumber untuk regex: http://montreal.pm.org/tech/neil_kandalgaonkar.shtml

Gowtham
sumber
2
menginspirasi saya untuk menulis versi perl6. juga, 1000000dapat ditulis10**6
pabo
1
Juga, 1000000 dapat ditulis 1E6
mob
Memperbarui jawaban saya. Terima kasih @mob
Gowtham
Selalu menjadi regex favorit saya, tetapi Anda harus ingat bahwa itu gagal secara spektakuler begitu Anda mencapai angka yang lebih tinggi - karena fakta bahwa itu mengubah angka besar menjadi unary. Regex ini mungkin tidak berfungsi untuk menemukan bilangan prima dalam ratusan ribu dan lebih, tergantung pada konfigurasi bahasa seseorang (dan mesin Anda.)
Codefun64
7

Julia, 11

primes(10^6)

Sepertinya built in semakin upvotes, ditambah saya membutuhkan lebih banyak kata untuk jawaban yang lebih lama.

gggg
sumber
7

J (15 atau 9)

Saya tidak percaya ini mengalahkan Mathematica (bahkan jika itu hanya satu per 2 karakter)

a#~1 p:a=:i.1e6

Atau:

p:i.78498
ɐɔıʇǝɥʇu
sumber
1
... The output format should be one number per line of output.Itu sebabnya jawaban saya dimulai dengan 1[\ .
Gareth
6

gs2, 5 byte

Dikodekan dalam CP437:

∟)◄lT

1C 29mendorong satu juta, 11 6Cadalah bilangan prima di bawah ini, 54adalah menunjukkan garis.

Lynn
sumber
5

GolfScript, 22/20 (20/19) byte

n(6?,:|2>{(.p|%-.}do:n

Dengan mengorbankan kecepatan, kode dapat dibuat dua byte lebih pendek:

n(6?,:|2>.{|%2>-}/n*

Jika format output yang ditentukan dalam pertanyaan yang diedit diabaikan (yang merupakan jawaban dari banyak jawaban yang ada), dua byte dapat disimpan dalam versi cepat dan satu dapat disimpan dalam versi lambat:

n(6?,:|2>{(.p|%-.}do
n(6?,:|2>.{|%2>-}/`

Ini akan mencetak LF tambahan setelah bilangan prima untuk versi cepat, dan itu akan mencetak bilangan prima sebagai larik untuk yang lambat.

Bagaimana itu bekerja

Kedua versi ini merupakan implementasi dari saringan Eratosthenes .

Versi cepat melakukan hal berikut:

  1. Atur A = [ 2 3 4 … 999,999 ]dan | = [ 0 1 2 … 999,999 ].

  2. Atur N = A[0]dan cetak N.

  3. Kumpulkan setiap elemen ke-N dari |dalam C. Ini adalah kelipatan dari N.

  4. Setel A = A - C.

  5. Jika Atidak kosong, kembali ke 2.

n(6?   # Push "\n".pop() ** 6 = 1,000,000.
,:|    # Push | = [ 0 1 2 … 999,999 ].
,2>    # Push A = [ 2 3 4 … 999,999 ].
{      #
  (    # Unshift the first element (“N”) of “A”.
  .p   # Print “N”.
  |%   # Collect every N-th element from “A” into a new array, starting with the first.
  -    # Take the set difference of “A” and the array from above.
  .    # Duplicate the set difference.
}do    # If the set difference is non-empty, repeat.
:n     # Store the empty string in “n”, so no final LF will get printed.

Versi lambat bekerja dengan cara yang sama, tetapi alih-alih menghapus kelipatan minimum "A" (yang selalu prima), ia menghapus kelipatan semua bilangan bulat positif di bawah 1.000.000.

Daya saing

Dengan tidak adanya fungsi matematika bawaan untuk memfaktisasi atau memeriksa primality, semua solusi GolfScript akan sangat besar atau sangat tidak efisien.

Meskipun masih jauh dari efisien, saya pikir saya telah mencapai rasio kecepatan-ke-ukuran yang layak. Pada saat pengajuannya, pendekatan ini tampaknya menjadi yang terpendek dari mereka yang tidak menggunakan salah satu built-in yang disebutkan di atas. Saya katakan sepertinya karena saya tidak tahu bagaimana beberapa jawaban bekerja ...

Saya telah membandingkan keempat solusi GolfScript yang diajukan: w0lf's (divisi percobaan), jawaban saya yang lain (teorema Wilson) dan dua jawaban ini. Inilah hasilnya:

Bound     | Trial division     | Sieve (slow)       | Wilson's theorem | Sieve (fast)
----------+--------------------+--------------------+------------------+----------------
1,000     | 2.47 s             | 0.06 s             | 0.03 s           | 0.03 s
10,000    | 246.06 s (4.1 m)   | 1.49 s             | 0.38 s           | 0.14 s
20,000    | 1006.83 s (16.8 m) | 5.22 s             | 1.41 s           | 0.38 s
100,000   | ~ 7 h (estimated)  | 104.65 (1.7 m)     | 35.20 s          | 5.82 s
1,000,000 | ~ 29 d (estimated) | 111136.97s (3.1 h) | 3695.92 s (1 h)  | 418.24 s (7 m)
Dennis
sumber
Apakah saringan "lambat" hanyalah Saringan Eratosthenes?
dorukayhan
Keduanya. Versi lambat hanyalah implementasi yang mengerikan.
Dennis
5

NARS2000 APL, 7 karakter

⍸0π⍳1e6
Sarang
sumber
3
Selamat Datang di Programming Puzzles & Code Golf!
Dennis
4

Golfscript 26 25 24

Sunting (satu arang tersimpan lagi berkat Peter Taylor):

10 6?,{:x,{)x\%!},,2=},`

Kode lama:

10 6?,{.,{)\.@%!},,2=*},`

Kode ini hanya memiliki nilai teoritis, karena sangat lambat dan tidak efisien. Saya pikir itu bisa memakan waktu berjam-jam untuk berjalan.

Jika Anda ingin mengujinya, coba misalnya hanya bilangan prima hingga 100:

10 2?,{:x,{)x\%!},,2=},`
Cristian Lupascu
sumber
Anda dapat menyimpan karakter dengan mengganti \;dengan *. (Anda juga bisa mendapatkan lebih cepat untuk penghitungan karakter saat ini dengan menemukan pembagi pertama daripada semuanya:10 6?,2>{.),2>{1$\%!}?=},`
Peter Taylor
@PeterTaylor Terima kasih, menggunakan perkalian ada trik yang sangat rapi.
Cristian Lupascu
Ada satu lagi char save dengan variabel: ganti .,dengan :x,dan \.@dengan x\ (spasi putih adalah karena melarikan diri masalah dengan MD dalam komentar) dan menghapus *.
Peter Taylor
@PeterTaylor bagus, terima kasih! Saya telah mengedit kode saya.
Cristian Lupascu
4

CJam - 11

1e6,{mp},N*

1e6,- array 0 ... 999999
{mp},- pilih bilangan prima
N*- gabung dengan baris baru

aditsu
sumber
1
Bukankah CJam lebih baru dari pertanyaan ini?
Peter Taylor
@PeterTaylor oh, ya itu
aditsu
4

GolfScript, 25 (24) byte

!10 6?,2>{.(@*.)@%!},n*\;

Jika format output yang ditentukan dalam pertanyaan yang diedit diabaikan, satu byte dapat disimpan:

!10 6?,2>{.(@*.)@%!},`\;

Ini akan mencetak bilangan prima sebagai array (seperti banyak solusi lain lakukan) daripada satu per baris.

Bagaimana itu bekerja

Gagasan umum adalah menggunakan teorema Wilson , yang menyatakan bahwa n > 1 adalah prima jika dan hanya jika

                                                      (n - 1)!  = -1 (mod n)

!     # Push the logical NOT of the empty string (1). This is an accumulator.
10 6? # Push 10**6 = 1,000,000.
,2>   # Push [ 2 3 4 … 999,999 ].
{     # For each “N” in this array:
  .(  # Push “N - 1”.
  @   # Rotate the accumulator on top of the stack.
  *   # Multiply it with “N - 1”. The accumulator now hold “(N - 1)!”.
  .)  # Push “(N - 1)! + 1”
  @   # Rotate “N” on top of the stack.
  %!  # Push the logical NOT of “((N - 1)! + 1) % N”.
},    # Collect all “N” for which “((N - 1)! + 1) % N == 0” in an array.
n*    # Join that array by LF.
\;    # Discard the accumulator.

Tolak ukur

Lebih cepat dari pembagian percobaan, tetapi lebih lambat dari ayakan Eratosthenes. Lihat jawaban saya yang lain .

Dennis
sumber
4

Java, 110 byte

void x(){for(int i=1;i++<1e6;)System.out.print(new String(new char[i]).matches(".?|(..+?)\\1+")?"":(i+"\n"));}

Menggunakan pembagian unary melalui regex sebagai tes primality.

Addison Crump
sumber
1
Pendekatan yang bagus. Belum pernah melihat prime-regex sebelumnya. +1 dari saya. Meskipun, menggunakan nested for-loop untuk pengecekan prime sedikit lebih pendek . :)
Kevin Cruijssen
3

C, 91 88 85 82 81 80 76 72 karakter

main(i,j,b){for(;i++<1e6;b++&&printf("%d\n",i))for(j=2;j<i;)b=i%j++&&b;}

Algoritma ini sangat tidak efisien, tetapi karena kita melakukan golf kode yang seharusnya tidak masalah.

Gareth
sumber
1
Anda dapat mempersingkat dengan mudah: main(i,j,b){for(;i++<1e6;b++&&printf("%d\n",i))for(j=2;j<i;)b=i%j++&&b;}atau beberapa ide seperti ini (karena saya sebenarnya tidak mengkompilasinya)
Ali1S232
Bagaimana imenjadi 0? Saya pikir, jika Anda memberikan setiap argumen, itu akan gagal. Juga, saya pikir jakan memiliki semacam kesalahan tipe. Tapi tidak yakin b.
Erik the Outgolfer
3

Mathematica 25

Dengan asumsi Anda tidak tahu jumlah bilangan prima kurang dari 10 ^ 6:

Prime@Range@PrimePi[10^6]
DavidC
sumber
3

J, 16 karakter

1]\(#~1&p:)i.1e6

Tanpa persyaratan format output, ini dapat dikurangi menjadi 13 karakter:

(#~1&p:)i.1e6

1]\ hanya mengambil array peringkat 1 dari bilangan prima, mengubahnya menjadi array peringkat 2, dan menempatkan setiap prime pada barisnya sendiri - sehingga format output default interpreter mengubah daftar satu baris menjadi satu prima per baris.

(#~ f) ypada dasarnya filter, di mana fmengembalikan boolean untuk setiap elemen dalam y. i.1e6adalah kisaran bilangan bulat [0,1000000), dan 1&p:merupakan fungsi boolean yang mengembalikan 1 untuk bilangan prima.

rasionalis
sumber
3

R, 45 43 karakter

for(i in 2:1e6)if(sum(!i%%2:i)<2)cat(i," ")

Untuk setiap angka x dari 2 hingga 1e6, cukup keluarkan jika jumlah x mod 2 hingga x yang sama dengan 0 kurang dari 2.

plannapus
sumber
Angka pertama yang dihasilkan oleh kode ini adalah 1, tetapi 1 bukan bilangan prima.
Sven Hohenstein
@SvenHohenstein Terima kasih, diperbaiki.
plannapus
3

Bash (433643)

Upaya saya (tidak begitu pintar) adalah menggunakan faktor untuk faktor produk.

factor ${PRODUCT}

Sayangnya dengan jumlah besar produknya tentu saja besar. Butuh waktu lebih dari 12 jam untuk berlari. Saya memutuskan untuk mempostingnya karena saya pikir itu unik.

Ini kode lengkapnya.

Jika bilangan prima di bawah enam itu akan masuk akal.

  factor 30

Oh well, saya sudah mencoba.

Kevin Cox
sumber
+1 Jawaban ini benar-benar jahat. Tidak cukup hasil perhitungan (ini menghemat sedikit karakter), dan jauh lebih buruk untuk dihitung :) Ini sangat mungkin juga contoh yang membuat kinerja yang dioptimalkan factorjauh lebih buruk daripada algoritma pembagian percobaan dasar.
orion
3

C #, 70

Enumerable.Range(1,1e6).Where(n=>Enumerable.Range(2,n).All(x=>x%n!=0))

Anda tidak akan melihat banyak di sini meskipun untuk waktu yang lama ...

Itu adalah Notalie.
sumber
Ada beberapa alasan mengapa ini salah. (1) Anda tidak dapat secara implisit mengkonversi dari double 1e6ke int, tetapi intdiharuskan oleh Range. (2) Batin Rangeharus paling tidak menerima n-2syarat, jika tidak Anda akan menguji n % nyang jelas 0. (3) Anda menulis x%nkapan pun Anda mau n%x. Memperbaiki masalah ini, sesuatu seperti ini akan berfungsi: Enumerable.Range(2,999999).Where(n=>Enumerable.Range(2,n-2).All(x=>n%x!=0))Namun, ini masih tidak menghasilkan angka; persyaratannya satu per baris.
Jeppe Stig Nielsen