La question

Un nombre premier de Sophie Germain est un nombre premier p tel que 2p + 1 est également un nombre premier. Par exemple, 11 est un nombre premier de Sophie Germain, car 23 est également un nombre premier. Écrivez le programme le plus court pour calculer les nombres premiers de Sophie Germain dans l'ordre croissant

Règles

• Les nombres premiers de Sophie Germain doivent être générés par votre programme, pas à partir d'une source externe.
• Votre programme doit calculer tous les nombres premiers de Sophie Germain inférieurs à 2³²-1
• Vous devez imprimer chaque prime Sophie Germain distincte trouvée par votre programme.
• La personne avec le score le plus bas gagne

Notation

• 2 points par octet de votre code
• -10 si vous pouvez afficher un nombre premier généré par votre programme supérieur à 2³²-1

CJam

Pour 17 caractères, nous obtenons une énumération complète jusqu'à 2 ^ 32:

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

Pour 4 caractères de plus, nous obtenons une plage juste assez large pour inclure un SG prime supérieur à 2 ^ 32:

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

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

Bien sûr, nous pourrions également étendre la gamme gratuitement

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

Pyth, 19 octets * 2 - 10 = 28

Notez que le compilateur / exécuteur en ligne n'affiche pas de sortie car il s'agit d'une boucle infinie.

K1#~K1I&!tPK!tPhyKK

Expliqué:

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

Pyth - 2 * 16 octets - 10 = 22

Utilise la méthode habituelle de vérification de prime en Pyth avec le !tPet l'applique à la fois au nombre et à son nombre sûr, avec une petite astuce pour vérifier les deux à la fois. Va jusqu'à 10^10, donc je vais pour le bonus.

f!+tPTtPhyTr2^TT

Explication à venir.

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

Essayez moins de 1000 en ligne .

#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;
    }
}

CJam, 34 (2 * 22 - 10)

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

Imprime tous les nombres premiers de Sophie Germain sous 12 ** 9, ce qui inclut 4294967681 > 2 ** 32.

J'estime que cela prendra environ 8 heures sur ma machine. Je vais l'exécuter ce soir.

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]

iest un chèque de choix. pprend tous les nombres noù les deux net 2*x+1sont premiers. pest une liste infinie.

Edit: meilleure façon de vérifier si 2*n+1est premier.

Julia, 2 * 49 - 10 = 88

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

Les imprime sous forme de liste, [2,3,5,11,...]. Si ce format, en utilisant la primesfonction ou en attendant que tout le calcul soit fait pour imprimer ne soit pas acceptable, cela les imprime un par ligne pendant son exécution.

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

C'est un peu plus long, 52 caractères. Les deux calculent tous les nombres premiers de Sophie Germain jusqu'à 2^33, ils devraient donc obtenir la remise de 10 points.

Python 3, 124 123 octets

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

Comment ça marche?

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)

Essayez-le en ligne ici .

Mon ordinateur indique qu'il a généré 0,023283% de tous les nombres premiers de Sophie Germain inférieurs à 2 ^ 32.

Une fois terminé, je le posterai sur pastebin s'il y a suffisamment de lignes. Vous pouvez l'utiliser pour vérifier que vous les avez tous.

Perl, 2 * 57-10 = 104

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

2
3
5
11
...
8589934091
8589934271

42 secondes à 2 ^ 32, 1m26s à 2 ^ 33. S'exécutera 50% plus rapidement s'il 2*$_+1est écrit en tant que 1+$_<<1mais c'est un octet de plus.

Le module installe également de primes.plnombreux filtres dont un pour les nombres premiers de Sophie-Germain. Donc: primes.pl --so 2**33(20 octets)

Rubis, 61 * 2 - 10 = 112

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

Il faudrait une éternité pour imprimer toutes les valeurs jusqu'à 2 ** 32

Éditer

Rasé de quelques octets en remplaçant Float :: INFINITY pour 1.0 / 0

PARI / GP, 46 * 2 - 10 = 82

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