Introducción
La espiral de Ulam es una representación gráfica del conjunto de números primos, ideada por el matemático Stanislaw Ulam. Se construye escribiendo los números enteros positivos en una espiral cuadrada y marcando especialmente los números primos. Puedes leer más sobre esto aquí.
Pero vamos a calcular en la versión alternativa de esta espiral donde los números primos están alineados en la espiral en lugar de los números naturales como en la espiral de Ulam original.
Los números primos se escriben en forma de espiral comenzando desde el origen (0, 0) y moviéndose como se muestra en el diagrama de arriba. Los números que se muestran en la columna derecha y la fila inferior son los números de columna y los números de fila respectivamente (es decir, coordenadas yyx)
El objetivo es encontrar la posición (coordenadas xey) de un número primo dado.
Ejemplos:
Input : 5 Output : 1 1 As per the diagram above 5 corresponds to the column 1 and row 1. Input : 11 Output : -1 1 Similarly, 11 will correspond to column -1 and row 1.
Enfoque: La solución general al problema sería crear un algoritmo para predecir la posición del punto de la espiral en movimiento en cada paso y hacer referencia a cada paso de la espiral a un número primo (por ejemplo, paso 0 -> 2; paso 1 -> 3 ; paso 2 –> 5 y así sucesivamente). Usando este número primo podemos rastrear hasta las coordenadas cuál es nuestra solución (2 –> [0, 0], 3 –> [1, 0], 5 –> [1, 1]).
Comenzamos contando x e y, para el paso k = 1: x = y = 0. k = 2 lleva a aumentar x en 1 (x = 1) luego viene k = 3 proporcionando y = 1. Ahora como el gira la espiral debemos disminuir los valores ahora en 2. Los movimientos consecutivos se muestran a continuación:
A partir de los cálculos anteriores, observamos que las operaciones son las mismas para un lote de pasos, por ejemplo, al principio K = 2 y 3 sigue uno donde x aumenta en 1 y luego y en 1. Luego en K= 4, 5, 6, 7 para 4 y 5, x disminuye e y disminuye en K = 6 y 7. De nuevo desde K = 8, 9 y 10, x aumenta en pasos repetidos y 11, 12, 13 consiste en disminuir y.
Cada paso se puede clasificar en un lote y el tamaño del lote aumenta en 1 después de dos ejecuciones. Después de una ejecución, la operación cambia de y a x o viceversa y después de cada dos ejecuciones por lotes, la operación de suma se cambia a resta y viceversa. La siguiente tabla lo explica.
Por último, también necesitamos crear un generador de números primos que seguirá alimentando el algoritmo anterior con un número primo al que se hará referencia en el paso correspondiente y nos dará las coordenadas requeridas.
Aquí está la implementación de la idea anterior:
Límites de entrada: 2 < N < 1000000
Suposición: Los números primos son las únicas entradas al programa.
C++
// C++ Program to find coordinates of a
// prime number in a Prime Spiral
#include <bits/stdc++.h>
using namespace std;
// The main algorithm that keeps track of
// coordinates
void spiralSplicer(int input)
{
// Batch size tracker
int step_count = 1;
// Batch size limiter
int step_limit = 2;
// switches between -1 and +1
int adder = 1;
// Co-ordinates of step K
int x = 0, y = 0;
for (int n = 2; n != input + 1; n++,
step_count++) {
// Keeps track of steps
// Checks on the current batch
if (step_count <= .5 * step_limit)
x += adder; // Switch to operating on x
else if (step_count <= step_limit)
y += adder; // Switch to operating on x
if (step_count == step_limit) {
// Changes adder to -1 and vice versa
adder *= -1;
// Keeps on updating 'step_limit'
step_limit += 2;
// Resets count
step_count = 0;
}
}
cout << x << " " << y;
}
int primeIndex(int input)
{
int j, cnt, prime_c = 0;
for (int i = 2; i <= 1000000; i++) {
cnt = 0;
for (j = 2; j <= i; j++) {
if (i % j == 0)
cnt++;
}
if (cnt == 1) {
prime_c++;
if (input == i) {
/* Replaces the prime number with
Step K which will be fed into
the main algorithm*/
input = prime_c;
break;
}
}
}
return input;
}
// driver code
int main()
{
int input = 113;
// Prime Index Finder Output ported
// to final algorithm
spiralSplicer(primeIndex(input));
}
Java
// java Program to find coordinates of a
// prime number in a Prime Spiral
public class GFG {
// The main algorithm that keeps track of
// coordinates
static void spiralSplicer(int input)
{
// Batch size tracker
int step_count = 1;
// Batch size limiter
int step_limit = 2;
// switches between -1 and +1
int adder = 1;
// Co-ordinates of step K
int x = 0, y = 0;
for (int n = 2; n != input + 1;
n++, step_count++)
{
// Keeps track of steps
// Checks on the current batch
if (step_count <= .5 * step_limit)
// Switch to operating on x
x += adder;
else if (step_count <= step_limit)
// Switch to operating on x
y += adder;
if (step_count == step_limit)
{
// Changes adder to -1 and
// vice versa
adder *= -1;
// Keeps on updating 'step_limit'
step_limit += 2;
// Resets count
step_count = 0;
}
}
System.out.print( x + " " + y);
}
static int primeIndex(int input)
{
int j, cnt, prime_c = 0;
for (int i = 2; i <= 1000000; i++)
{
cnt = 0;
for (j = 2; j <= i; j++)
{
if (i % j == 0)
cnt++;
}
if (cnt == 1)
{
prime_c++;
if (input == i)
{
/* Replaces the prime
number with Step K which
will be fed into
the main algorithm*/
input = prime_c;
break;
}
}
}
return input;
}
// Driver code
public static void main(String args[]) {
int input = 113;
// Prime Index Finder Output ported
// to final algorithm
spiralSplicer(primeIndex(input));
}
}
// This code is contributed by Sam007.
Python
# Python Program to find coordinates of a # prime number in a Prime Spiral # The main algorithm that keeps track of # coordinates def spiralSplicer(inp): # Batch size tracker step_count = 1 # Batch size limiter step_limit = 2 # switches between -1 and +1 adder = 1 # Co-ordinates of step K x, y = 0, 0 for n in range(2, inp + 1): # Keeps track of steps # Checks on the current batch if (step_count <= .5 * step_limit): x += adder # Switch to operating on x else if (step_count <= step_limit): y += adder # Switch to operating on x if (step_count == step_limit): # Changes adder to -1 and vice versa adder *= -1 # Keeps on updating 'step_limit' step_limit += 2 # Resets count step_count = 0 step_count += 1 print x, y def primeIndex(inp): cnt, prime_c = 0, 0 for i in range(2, 1000000 + 1): cnt = 0 for j in range(2, i + 1): if (i % j == 0): cnt += 1 if (cnt == 1): prime_c += 1 if (inp == i): """ Replaces the prime number with Step K which will be fed into the main algorithm """ inp = prime_c break return inp # driver code inp = 113 # Prime Index Finder Output ported # to final algorithm temp = primeIndex(inp) spiralSplicer(temp) #This code is contributed by Sachin Bisht
C#
// C# Program to find coordinates of a
// prime number in a Prime Spiral
using System;
class GFG {
// The main algorithm that keeps track of
// coordinates
static void spiralSplicer(int input)
{
// Batch size tracker
int step_count = 1;
// Batch size limiter
int step_limit = 2;
// switches between -1 and +1
int adder = 1;
// Co-ordinates of step K
int x = 0, y = 0;
for (int n = 2; n != input + 1;
n++, step_count++)
{
// Keeps track of steps
// Checks on the current batch
if (step_count <= .5 * step_limit)
// Switch to operating on x
x += adder;
else if (step_count <= step_limit)
// Switch to operating on x
y += adder;
if (step_count == step_limit)
{
// Changes adder to -1 and
// vice versa
adder *= -1;
// Keeps on updating 'step_limit'
step_limit += 2;
// Resets count
step_count = 0;
}
}
Console.Write( x + " " + y);
}
static int primeIndex(int input)
{
int j, cnt, prime_c = 0;
for (int i = 2; i <= 1000000; i++)
{
cnt = 0;
for (j = 2; j <= i; j++)
{
if (i % j == 0)
cnt++;
}
if (cnt == 1)
{
prime_c++;
if (input == i)
{
/* Replaces the prime
number with Step K which
will be fed into
the main algorithm*/
input = prime_c;
break;
}
}
}
return input;
}
// Driver code
public static void Main ()
{
int input = 113;
// Prime Index Finder Output ported
// to final algorithm
spiralSplicer(primeIndex(input));
}
}
// This code is contributed by Sam007.
PHP
<?php
// PHP Program to find coordinates of a
// prime number in a Prime Spiral
// The main algorithm that
// keeps track of
// coordinates
function spiralSplicer($input)
{
// Batch size tracker
$step_count = 1;
// Batch size limiter
$step_limit = 2;
// switches between -1 and +1
$adder = 1;
// Co-ordinates of step K
$x = 0; $y = 0;
for ($n = 2; $n != $input + 1; $n++,
$step_count++)
{
// Keeps track of steps
// Checks on the current batch
if ($step_count <= .5 * $step_limit)
// Switch to operating on x
$x += $adder;
else if ($step_count <= $step_limit)
// Switch to operating on x
$y += $adder;
if ($step_count == $step_limit)
{
// Changes adder to -1
// and vice versa
$adder *= -1;
// Keeps on updating
// 'step_limit'
$step_limit += 2;
// Resets count
$step_count = 0;
}
}
echo $x, " ", $y;
}
function primeIndex($input)
{
$j;
$cnt;
$prime_c = 0;
for ($i = 2; $i <= 1000000; $i++)
{
$cnt = 0;
for ($j = 2; $j <= $i; $j++)
{
if ($i % $j == 0)
$cnt++;
}
if ($cnt == 1)
{
$prime_c++;
if ($input == $i)
{
// Replaces the prime
// number with Step K
// which will be fed into
// the main algorithm
$input = $prime_c;
break;
}
}
}
return $input;
}
// Driver Code
$input = 113;
// Prime Index Finder Output ported
// to final algorithm
spiralSplicer(primeIndex($input));
// This Code is contributed by ajit
?>
Javascript
<script>
// Javascript Program to find coordinates of a
// prime number in a Prime Spiral
// The main algorithm that keeps track of
// coordinates
function spiralSplicer(input)
{
// Batch size tracker
let step_count = 1;
// Batch size limiter
let step_limit = 2;
// switches between -1 and +1
let adder = 1;
// Co-ordinates of step K
let x = 0, y = 0;
for (let n = 2; n != input + 1; n++, step_count++)
{
// Keeps track of steps
// Checks on the current batch
if (step_count <= .5 * step_limit)
// Switch to operating on x
x += adder;
else if (step_count <= step_limit)
// Switch to operating on x
y += adder;
if (step_count == step_limit)
{
// Changes adder to -1 and
// vice versa
adder *= -1;
// Keeps on updating 'step_limit'
step_limit += 2;
// Resets count
step_count = 0;
}
}
document.write( x + " " + y);
}
function primeIndex(input)
{
let j, cnt, prime_c = 0;
for (let i = 2; i <= 1000000; i++)
{
cnt = 0;
for (j = 2; j <= i; j++)
{
if (i % j == 0)
cnt++;
}
if (cnt == 1)
{
prime_c++;
if (input == i)
{
/* Replaces the prime
number with Step K which
will be fed into
the main algorithm*/
input = prime_c;
break;
}
}
}
return input;
}
let input = 113;
// Prime Index Finder Output ported
// to final algorithm
spiralSplicer(primeIndex(input));
</script>
Producción :
3 2
Este artículo es una contribución de Pritom Gogoi . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA