Daftar bilangan prima Sophie Germain

10

Pertanyaan

Sebuah Sophie Germain utama adalah prima p sehingga 2p + 1 adalah prima juga. Misalnya, 11 adalah prime Sophie Germain karena 23 juga prima. Tulis program terpendek untuk menghitung bilangan prima Sophie Germain dalam urutan menaik

Aturan

  • Bilangan prima Sophie Germain harus dihasilkan oleh program Anda , bukan dari sumber eksternal.
  • Program Anda harus menghitung semua bilangan prima Sophie Germain di bawah 2³²-1
  • Anda harus mencetak setiap Sophie Germain utama yang ditemukan program Anda.
  • Orang dengan skor terendah menang

Mencetak gol

  • 2 poin per byte kode Anda
  • -10 jika Anda dapat menampilkan prime yang dihasilkan oleh program Anda lebih besar dari 2³²-1
Meow Mix
sumber
Komentar bukan untuk diskusi panjang; percakapan ini telah dipindahkan ke obrolan .
Martin Ender

Jawaban:

4

CJam

Untuk 17 karakter, kami mendapatkan penghitungan penuh hingga 2 ^ 32:

G8#,{_mp*2*)mp},`

Untuk 4 karakter lebih, kami mendapatkan rentang yang cukup besar untuk menyertakan perdana SG yang lebih besar dari 2 ^ 32:

G8#K_*+,{_mp*2*)mp},`

sejak 4294967681 = 2 ^ 32 + 385 <2 ^ 32 + 400.

Tentu saja, kami dapat memperluas rentang sama dengan gratis seperti

C9#,{_mp*2*)mp},`
Peter Taylor
sumber
Ini berarti Anda dapat mengirimkannya tanpa bonus untuk 17 karakter atau dengan bonus untuk 21 karakter
Meow Mix
@ user3502615, atau dengan bonus untuk 17 karakter. Meskipun masih bisa diperdebatkan apakah daftar SG prime I benar-benar dihasilkan "oleh program saya", karena saya tidak memiliki komputer yang cukup kuat untuk menjalankannya sejauh itu.
Peter Taylor
I,memperlakukan Isebagai integer 32-bit yang ditandatangani, sehingga nilai maksimumnya Iadalah 2 ** 31 - 1.
Dennis
2
@ Dennis, apakah itu properti yang didokumentasikan dari bahasa tersebut atau kekhasan implementasi dari implementasi Java?
Peter Taylor
Ini tidak didokumentasikan, tetapi perilaku ini konsisten untuk Java dan penerjemah online.
Dennis
3

Pyth, 19 byte * 2 - 10 = 28

Perhatikan bahwa kompiler / pelaksana online tidak menampilkan keluaran karena ini merupakan loop tak terbatas.

K1#~K1I&!tPK!tPhyKK

Dijelaskan:

K1                      K=1
  #                     While true:
   ~K1                  K+=1
      I                 If
       &                logical AND
        !tPK            K is prime
            !tPhyK      2*K+1 is prime (y is double, h is +1)
                  K     Print K
mbomb007
sumber
PZtidak mengembalikan nilai yang benar atau salah. Ini mengembalikan faktorisasi utama Z. Pengujian untuk prima adalah !tPZ, yang memeriksa apakah faktorisasi prima hanya berisi satu faktor.
Jakube
Iya. Sekarang berhasil. !tPkesalahan 0dan 1menjadi prima, karena faktorisasi prima mereka hanya berisi 1 faktor. Perbaikan mudah adalah dengan mengganti semua Zdengan Kdan menetapkan K2di awal.
Jakube
Beberapa golf lain: tetapkan K1alih-alih K2, dan tukarkan jika dan kenaikannya. Dengan cara ini Anda dapat menghapus ). Dan +1*K2sama halnya dengan hyK.
Jakube
Ah, saya baru saja membaca tentang itu di halaman tutorial. Apakah itu berfungsi untuk Anda di pyth.herokuapp.com/?code=K2%23I%26!tPK!tPhyKK)~K1&debug=0
mbomb007
Kompilator online tidak menunjukkan hasil, karena program macet dalam loop tak terbatas. Dan situs web hanya menampilkan output, setelah program selesai. Saya telah menguji kode menggunakan kompiler offline. Berhasil.
Jakube
1

Pyth - 2 * 16 byte - 10 = 22

Menggunakan metode pemeriksaan perdana prima di Pyth dengan !tPdan menerapkannya baik untuk nomor dan safe-prime, dengan sedikit trik untuk memeriksa keduanya sekaligus. Naik 10^10, jadi saya akan mendapatkan bonus.

f!+tPTtPhyTr2^TT

Penjelasan segera hadir.

f          r2^TT     Filter from 2 till 10^10
 !                   Logical not to detect empty lists
  +                  List concatenation
   tP                All but the firs element of the prime factorization
    T                The filter element
   tP                All but the firs element of the prime factorization
    hyT              2n+1

Coba di bawah 1000 online .

Maltysen
sumber
1
Ini membutuhkan mesin dengan sekitar 40 GB memori RAM. ; Cukup efisien ;-)
Jakube
Saya tidak berpikir Anda dapat mengklaim - 10 kecuali Anda benar-benar berhasil menjalankan kode?
orlp
@ orlp tidak, saya bertanya OP dan dia berkata membuat rentang lebih kecil dan mensimulasikan seluruh program akan cukup: chat.stackexchange.com/transcript/message/21585393#21585393
Maltysen
1
#include<stdio.h>
#include<math.h>

int isprime(int);
int main(){
    int check,n,secondcheck;
    printf("enter how long you want to print\n");
    scanf("%d",&n);
    for(int i=2;i<n;i++){
        check = isprime(i);
        if(check==0){
        secondcheck = isprime(2*i+1);
        if(secondcheck==0){
        printf("%d\t",i);
        }
        else
        continue;
        }
    }
}
int isprime(int num){   
    int check = num,flag=0;
     num = sqrt(num);
    for(int i=2;i<=num;i++){
        if(check%i==0){
            flag=1;
            return 1;
        }
    }
    if(flag==0){
        return 0;
    }
}
pengguna45221
sumber
3
Silakan pertimbangkan bermain golf program Anda (dengan menghapus ruang ..etc) dan lihat seberapa jauh Anda bisa mendapatkan.
Mhmd
0

CJam, 34 (2 * 22 - 10)

C9#{ImpI2*)mp&{Ip}&}fI

Mencetak semua bilangan prima Sophie Germain di bawah 12 ** 9, yang mencakup 4294967681 > 2 ** 32.

Saya memperkirakan bahwa ini akan memakan waktu sekitar 8 jam pada mesin saya. Saya akan menjalankannya malam ini.

Dennis
sumber
0

Haskell, 2 * 54-10 = 98 132

i a=all((>0).rem a)[2..a-1]
p=[n|n<-[2..],i n,i$2*n+1]

iadalah cek utama. pmengambil semua angka di nmana keduanya ndan 2*x+1prima. padalah daftar tanpa batas.

Sunting: cara yang lebih baik untuk memeriksa apakah 2*n+1prime.

nimi
sumber
0

Julia, 2 * 49 - 10 = 88

p=primes(2^33)
print(p[map(n->isprime(2n+1),p)])

Mencetaknya dalam format daftar [2,3,5,11,...],. Jika format itu, menggunakan primesfungsi, atau menunggu sampai semua perhitungan dilakukan untuk mencetak tidak dapat diterima, ini mencetak satu per baris saat dijalankan.

isprime=f
for i=1:2^33;f(i)&&f(2i+1)&&println(i)end

Ini sedikit lebih lama, 52 karakter. Keduanya menghitung semua bilangan prima Sophie Germain hingga 2^33, sehingga mereka harus mendapatkan diskon 10 poin.

Andrew
sumber
0

Python 3, 124 123 byte

i=3
q=[2]
while 1:
 p=1
 for x in range(2,round(i**.5)+1):p=min(p,i%x)
 if p:
  q+=[i];s=(i-1)/2
  if s in q:print(s)
 i+=2

Bagaimana cara kerjanya?

i=3                                 # Start at 3
q=[2]                               # Create list with first prime (2), to be list of primes.
while 1:                            # Loop forever
 p=1                                # Set p to 1 (true)
 for x in range(2,round(i**0.5)+1): # Loop from 2 to the number's square root. x is the loop value
     p=min(p,i%x)                   # Set p to the min of itself and the modulo of
                                    # the number being tested and loop value (x).
                                    # If p is 0 at the end, a modulo was 0, so it isn't prime.
 if p:                              # Check if p is 0
  q+=[i]                            # Add the current number (we know is prime) to list of primes (q)
  s=(i-1)/2                         # Generate s, the number that you would double and add 1 to make a prime.

  if s in q:print(s)                # If (i-1)/2 is a prime (in the list), then that prime satifies
                                    # the condition 2p+1 is prime because i is 2p+1, and i is prime
 i+=2                               # Increment by 2 (no even numbers are prime, except 2)

Cobalah online di sini .


Komputer saya mengatakan ini telah menghasilkan 0,023283% dari semua bilangan prima Sophie Germain di bawah 2 ^ 32.

Setelah selesai, saya akan mempostingnya di pastebin jika ada cukup baris. Anda dapat menggunakannya untuk memeriksa apakah Anda memiliki semuanya.

Tim
sumber
.5lebih pendek dari0.5
mbomb007
0

Perl, 2 * 57-10 = 104

use ntheory":all";forprimes{say if is_prime(2*$_+1)}2**33

2
3
5
11
...
8589934091
8589934271

42 detik hingga 2 ^ 32, 1m26s hingga 2 ^ 33. Akan berjalan 50% lebih cepat jika 2*$_+1ditulis sebagai 1+$_<<1tetapi itu satu byte lagi.

Modul ini juga menginstal primes.plyang memiliki banyak filter termasuk satu untuk bilangan prima Sophie-Germain. Jadi: primes.pl --so 2**33(20 byte)

DanaJ
sumber
0

Ruby, 61 * 2 - 10 = 112

require'prime';Prime.each(1.0/0)do|n|p Prime.prime?(n*2+1)end

Butuh selamanya untuk mencetak semua nilai hingga 2 ** 32

Edit

Dicukur beberapa byte menggantikan Float :: INFINITY untuk 1.0 / 0

Sheerforce
sumber
0

PARI / GP, 46 * 2 - 10 = 82

forprime(p=2,2^33,if(isprime(2*p+1),print(p)))
alephalpha
sumber