La soledad de los números primos

24

Recientemente leí la novela "La soledad de los números primos", donde los personajes principales se comparan de alguna manera con los números primos gemelos (" siempre juntos, pero nunca tocándose ").

Un primo gemelo es un número primo que es 2 menos o 2 más que otro número primo, por ejemplo, el par primo gemelo (41, 43). En otras palabras, un primo gemelo es un primo que tiene un espacio de primo de dos. Algunas veces el término primo gemelo se usa para un par de primos gemelos; un nombre alternativo para esto es primer gemelo o primer par. Wikipedia

Aunque no me gustó mucho la novela deprimente, y desde que he caído en PPCG últimamente, eso me planteó una pregunta ...

Tarea:

Dado un número entero positivo N> 4, encuentre los números primos solitarios (también conocidos como números primos aislados ) entre las parejas más cercanas de primos gemelos .

Tenga en cuenta que en este caso con el término números primos solitarios , me refiero a todos los números primos que no son primos gemelos y entre parejas de primos gemelos . Es por eso que N> 4 porque las dos primeras parejas de números primos son (3, 5) y (5, 7).

Ejemplo:

  1. N = 90.
  2. Encuentre las dos primeras parejas de primos gemelos <N y> N. Son: (71, 73) y (101, 103).
  3. Encuentra los primos solitarios en el rango> 73 y <101.
  4. Ellos son: 79, 83, 89, 97.

Casos especiales:

  • Si N está entre dos números primos gemelos, encuentre las parejas más cercanas de primos gemelos> N + 1 y <N-1. Ejemplo: N = 72, encuentre las parejas más cercanas de primos gemelos> 73 y <71 y luego excluya de la lista 71 y 73 porque no son primos solitarios . Entonces, para N = 72, el resultado esperado es: 67, 71 , 73 , 79, 83, 89, 97
  • Si N pertenece a un par de primos gemelos, por ejemplo N = 73, las parejas más cercanas de primos gemelos son (71, 73) y (101, 103). Si N = 71, las parejas más cercanas de primos gemelos son (59, 61) y (71, 73).

Casos de prueba:

N = 70   >  Lonely primes are:  67
N = 71   >  Lonely primes are:  67
N = 72   >  Lonely primes are:  67, 79, 83, 89, 97 (not the twins 71 and 73)
N = 73   >  Lonely primes are:  79, 83, 89, 97 
N = 90   >  Lonely primes are:  79, 83, 89, 97
N = 201  >  Lonely primes are:  211, 223
N = 499  >  Lonely primes are:  467, 479, 487, 491, 499, 503, 509

Reglas:

  • Escriba un programa o función completa que tome el número N de la entrada estándar.
  • Imprima la lista de primos solitarios en un formato legible como csv, list, array, etc.
  • El código más corto gana.
  • Incluya (cuando sea posible) un violín en línea comprobable.
Mario
fuente
44
¿Cuál es la salida esperada para entradas como 71, 72 o 73?
Martin Ender
1
Lonely Prime AKA Isolated Prime
Trauma digital
@ MartinEnder Extendí mi pregunta con casos especiales. Gracias por la aclaración.
Mario
1
Encuentro que los casos especiales estropean un poco el desafío (y se agregaron cuando ya se habían publicado algunas respuestas)
Luis Mendo
1
@ JonathanAllan Sí, puede considerar N> 4 porque las dos primeras parejas de números primos gemelos son (3, 5) y (5, 7). Agregué la especificación para que quede claro para todos.
Mario

Respuestas:

2

En realidad, 47 bytes

Esta solución trata el caso donde nestá entre dos primos gemelos, al verificar si el límite inferior es el mayor de un par de primos gemelos (eliminando que el primo gemelo a la izquierda de nosotros sea nuestro límite inferior) y si el límite superior es el más pequeño de un par de primos gemelos (eliminando el primo gemelo a la derecha de nosotros de ser nuestro límite superior). Para evitar que los primos gemelos se incluyan en nuestro rango una vez que tenemos los límites inferior y superior, necesitamos eliminar los primos pdonde p-2OR p+2son primos, de ahí el OR lógico y se niegan en el código.

Esto es un poco largo y probablemente se pueda jugar más golf. Sugerencias de golf bienvenidas. Pruébalo en línea!

╗1`╜+;⌐p@p&`╓F╜+1`╜-;¬p@p&`╓F╜-x`;;¬p@⌐p|Y@p&`░

Ungolfing

╗         Store implicit input n in register 0.

1`...`╓   Get the first value x for which the following function f returns a truthy value.
  ╜         Push n from register 0.
  +         Add x to n.
  ;⌐        Duplicate n+x and add 2 to a copy of n+x.
  p         Check if n+x+2 is prime.
  @p        Swap n+x to TOS and check if n+x is prime.
  &         Logical AND the two results.
F         Push the first (and only) result of previous filtering
╜+        Add that result to n to get the upper bound for our solitude.

1`...`╓   Get the first value x for which the following function f returns a truthy value.
  ╜         Push n from register 0.
  -         Subtract x from n.
  ;¬        Duplicate n-x and subtract 2 from a copy of n-x.
  p         Check if n-x-2 is prime.
  @p        Swap n-x to TOS and check if n-x is prime.
  &         Logical AND the two results.
F         Push the first (and only) result of previous filtering.
╜-        Subtract that result from n to get the lower bound for our solitude.

x`...`░   Push values of the range [a...b] where f returns a truthy value. Variable m.
  ;;        Duplicate m twice.
  ¬p        Check if m-2 is prime.
  @⌐p       Check if m+2 is prime. 
  |Y        Logical OR the results and negate.
             This eliminates any numbers with neighboring primes.
  @p        Check if m is prime.
  &         Logical AND primality_check(m) and the previous negation.
             This keeps every other prime number in the range.
Sherlock9
fuente
No obtengo la salida esperada 23cuando 24se da entrada . Los límites primos gemelos deben ser 17 / 19y 29 / 31, y 23es un primo aislado en el rango 19 .. 29.
AdmBorkBork
@TimmyD Oh, por amor a esolangs. O el error donde pdice que 25es primo aún no se ha solucionado, o Dennis no se ha retirado en realidad desde la corrección del error. Déjame ir a comprobar.
Sherlock9
@TimmyD Como la corrección de errores ya se completó, esta respuesta sigue siendo válida ya que el intérprete principal trabajó. Era solo que el intérprete en línea, Pruébalo en línea, aún no se había actualizado. Desde entonces se ha actualizado y TIO debería funcionar ahora.
Sherlock9
Sí, ¡gracias por la explicación!
AdmBorkBork
8

PowerShell v2 +, 237 149 147 231 216 181 174 169 166 bytes

param($n)filter f($a){'1'*$a-match'^(?!(..+)\1+$)..'}for($i=$n;!((f $i)-and(f($i+2)))){$i++}for(){if(f(--$i)){if((f($i-2))-or(f($i+2))){if($i-lt$n-1){exit}}else{$i}}}

Toma entrada $n. Define una nueva función fcomo la función primo regex (aquí devuelve un booleano si la entrada es primo o no).

La siguiente parte se establece $ipara ser igual a $n, luego gira hacia arriba hasta que encontremos la mitad inferior de nuestro límite superior de dos pares primos gemelos. Por ejemplo, para entrada 90, esto se detiene en $i=101.

Luego, giramos desde el límite superior hacia abajo. Lo sé, parece un bucle infinito, pero finalmente terminará.

Si el número actual es un número primo ( f(--$i)), pero su +/- 2 no es un número primo, añadimos $ia la tubería. Sin embargo, si +/- 2es un primo, verificamos si somos más bajos que $n-1(es decir, para tener en cuenta la situación cuando está dentro de un par primo gemelo), en ese momento nosotros exit. Al finalizar el programa, la tubería se imprime en la pantalla de forma implícita Write-Output.

Nota: debido a la estructura de bucle, imprime los números primos en orden descendente. OP ha aclarado que está bien.

Ejemplos

La salida aquí está separada por espacios, ya que ese es el método de stringificación predeterminado para una matriz.

PS C:\Tools\Scripts\golfing> 70,71,72,73,90,201,499,982|%{"$_ --> "+(.\the-solitude-of-prime-numbers.ps1 $_)}
70 --> 67
71 --> 67
72 --> 97 89 83 79 67
73 --> 97 89 83 79
90 --> 97 89 83 79
201 --> 223 211
499 --> 509 503 499 491 487 479 467
982 --> 1013 1009 997 991 983 977 971 967 953 947 941 937 929 919 911 907 887
AdmBorkBork
fuente
4

Haskell, 105 bytes

p x=all((>0).mod x)[2..x-1]
a%x=until(\z->p z&&p(z+2*a))(+a)x
f n=[x|x<-[(-1)%n+1..1%n-1],p x,1%x>x,(-1)%x<x]

Pruébalo en línea

Damien
fuente
3

JavaScript, 186 183 168 158 Bytes

// solution:
function d(d){function p(n){for(i=n;n%--i;);return!--i}u=d;for(;!p(d--)||!p(--d););for(;!p(u++)||!p(++u););for(;++d<u;)if(p(d)&&!p(d-2)&&!p(d+2))console.log(d)}

// runnable test cases:
console.info('Test ' + 70);
d(70);
console.info('Test ' + 71);
d(71);
console.info('Test ' + 72);
d(72);
console.info('Test ' + 73);
d(73);
console.info('Test ' + 90);
d(90);
console.info('Test ' + 201);
d(201);
console.info('Test ' + 499);
d(499);

usuario470370
fuente
Bienvenido a PPCG! Buena primera respuesta.
AdmBorkBork
2

PHP, 207 bytes

47 54 bytes para la is_primefunción que PHP no tiene. Vencería a Mathematica sin eso. :-RE

function p($n){for($i=$n>1?$n:4;$n%--$i;);return$i<2;}if(p($n=$argv[1])&p($n+2)|$z=p($n-1)&p($n+1))$n-=2;for($n|=1;!p($n)|!p($n-2);$n--);for($z++;$z--;$n+=2)for(;$n+=2;)if(p($n)){if(p($n+2))break;echo"$n,";}

correr con -r. imprime una coma final.

Descompostura

// is_prime function:
// loops from $n-1 down to 1, breaks if it finds a divisor.
// returns true if divisor is <2 (==1)
// special case $n==1: initialize $i=4 to prevent warnings
function p($n){for($i=$n>1?$n:4;$n%--$i;);return$i<2;}

// is $n between primes?
if($z=p(1+$n=$argv[1])&p($n-1)) // set $z to go to the _second_ twin pair above
    $n-=2;
// no:
else
    if(p($n)&p($n+2))$n-=2;     // $n is part of the upper pair
    // p($n)&p($n-2):           // $n is part of the lower pair
    // else:                    // this is a lonely (isolated) prime

// 1. find closest twins <=$n
for($n|=1;!p($n)|!p($n-2);$n--);

// 2. list primes until the next twin primes
L:
for(;$n+=2;)if(p($n))
    if(p($n+2))break;       // next twin primes found: break loop
    else echo"$n,";         // isolated prime: print

// 3. if ($z) repeat (once)
$n+=2;  // skip twin pair
if($z--)goto L;

Nota :

La is_primefunción en realidad devuelve truepara $n<2; pero al menos no produce una advertencia. Insertar $n=antes $n>1para arreglar.

Titus
fuente
php.net/manual/en/function.gmp-nextprime.php ¿ podría ayudar esta biblioteca?
Jörg Hülsermann
@ JörgHülsermann: si daría al menos 11 bytes, si gmp estaría en la instalación estándar. Intentalo.
Titus
1

Mathematica, 169 157 bytes

Select[PrimeQ]@Sort@Flatten@{If[q@#,0,#],Most@NestWhileList[i-=2;#+i&,#,!q@#&]&/@(i=3;q=PrimeQ@#&&Or@@PrimeQ[{2,-2}+#]&;#+{1,-1}(1+Boole@PrimeQ[{1,-1}+#]))}&
JungHwan Min
fuente
1

Raqueta 228 bytes

(λ(n)(let*((t 0)(lr(λ(l i)(list-ref l i)))(pl(drop(reverse(for/list((i(in-naturals))#:when(prime? i)#:final(and(> i n)
(= 2(- i t))))(set! t i)i))2)))(for/list((i(length pl))#:break(= 2(-(lr pl i)(lr pl(add1 i)))))(lr pl i))))

La desventaja de esta versión es que encuentra todos los números primos hasta N y no solo aquellos alrededor de N.

Versión sin golf:

(define (f n)
  (let* ((t 0)
         (lr (λ(l i) (list-ref l i)))
         (pl (drop(reverse  
                   (for/list ((i (in-naturals))
                              #:when (prime? i)
                              #:final (and
                                       (> i n)
                                       (= 2 (- i t))))
                     (set! t i)
                     i)) 2)))
    (for/list ((i (length pl))
               #:break (= 2 (- (lr pl i) (lr pl (add1 i)))) )
      (lr pl i)))
)

Pruebas:

(f 90)

Salida:

'(97 89 83 79)
rnso
fuente
1

Raqueta 245 bytes

(λ(n)(let((pl(reverse(let lp((n n)(t 0)(ol '()))(set! t(prev-prime n))(if(and(>(length ol)0)
(= 2(-(car ol)t)))(cdr ol)(lp t 0(cons t ol)))))))(let lq((n n)(t 0)(ol pl))(set! t(next-prime n))
(if(= 2(- t(car ol)))(cdr ol)(lq t 0(cons t ol))))))

Versión sin golf:

(require math)
(define f
  (lambda(n)
    (let ((pl 
           (reverse
            (let loop ((n n) (t 0) (ol '()))
              (set! t (prev-prime n))
              (if (and
                   (> (length ol) 0)
                   (= 2 (- (car ol) t)))
                  (cdr ol)
                  (loop t 0 (cons t ol)))))))
      (let loop2 ((n n) (t 0) (ol pl))
        (set! t (next-prime n))
        (if (= 2 (- t (car ol)))
            (cdr ol)
            (loop2 t 0 (cons t ol))))))
  )

(f 90)

Salida:

'(97 89 83 79)
rnso
fuente
1

Python 2.7: 160 bytes

t=lambda n:all(n%d for d in range(2,n))
def l(n):
 i=n
 while t(i)*t(i+2)-1:i+=1
 while t(n)*t(n-2)-1:n-=1
 print[x for x in range(n,i)if t(x)&~(t(x-2)|t(x+2))]

sugerencias son bienvenidas :)

Aaron
fuente