The prime numbers are written in a spiral form staring at (0,0) and moving as shown in the diagram below. The numbers shown on the right column and the bottom row are the column numbers and row numbers respectively (y and x coordinate frames). The objective is to find the position (x and y coordinates) of a given prime.
Input Format:
The input consists of multiple lines.
The first line gives the number of primes (N) in this test case.
The next N lines contain one prime in each line.
Output Format:
The output consists of N lines. Each consists of a space separated pair of integers giving the x and y coordinates of the corresponding prime in the input.
Constraints:
N≤10
Each prime < 1000000
Example 1
Input:
2
3
7
Output:
1 0
0 1
Explanation:
There are 2 primes in this test case (N=2). The primes are 3 and 7. The coordinates of these in the spiral is (1,0) and (0,1). The output hence has these in space separated form.
Example 2
Input:
3
5
11
13
Output:
1 1
1
1
1
0
Explanation:
There are 3 primes in this test case (N=2). The primes are 5, 11 and 13. The coordinates of these in the spiral is (1,1), (1,1) and (1,0). The output hence has these in space separated form.
Solution: In C
#include<stdio.h>
int prime[100];
int a[9][10],num,search[100];
void create()
{
int i=4,j=4,n=3,m=5,n1=5,m1=3,k=0,dire=0;
while(i!=-1)
{
a[i][j]=prime[k];
k++;
if(dire==0)
{
j++;
if(j==m)
{
m++;
dire=1;
}
}
else if(dire==1)
{
i--;
if(i==n)
{
n--;
dire=2;
}
}
else if(dire==2)
{
j--;
if(j==m1)
{
m1--;
dire=3;
}
}
else if(dire==3)
{
i++;
if(i==n1)
{
n1++;
dire=0;
}
}
}
for(k=0;k<num;k++)
{
for(i=0;i<9;i++)
{
for(j=0;j<10;j++)
{
if(a[i][j]==search[k])
{
printf("%d %d\n",j-4,4-i);//printing the position as required
}
}
}
}
}
int main()
{
int n, i = 3, count, c,j=0;
n=100;
//Reading Input
scanf("%d",&num);
for(j=0;j<num;j++)
scanf("%d",&search[j]);
j=0;
if ( n >= 1 )
{
prime[j]=2;
j++;
}
for ( count = 2 ; count <= n ; )
{
for ( c = 2 ; c <= i - 1 ; c++ )
{
if ( i%c == 0 )
break;
}
if ( c == i )
{
prime[j]=i;
j++;
count++;
}
i++;
}
create();
return 0;
}Solution: In Java
import java.util.*;
class Main {
static void spiralSplicer(int input)
{
Scanner ip=new Scanner(System.in);
int step_count = 1;
int step_limit = 2;
int adder = 1;
int x = 0, y = 0;
for (int n = 2; n != input + 1; n++, step_count++)
{
if (step_count <= .5 * step_limit) {
x += adder;
System.out.print(x);
}
else if (step_count <= step_limit)
y += adder;
if (step_count == step_limit)
{
adder *= -1;
step_limit += 2;
step_count = 0;
}
}
System.out.println(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)
{
input = prime_c;
break;
}
}
}
return input;
}
public static void main(String args[]) {
Scanner ip=new Scanner(System.in);
int input = ip.nextInt();
while(input-->0)
spiralSplicer(primeIndex(ip.nextInt()));
}
}Solution: In Python 3
def spiralSplicer(inp):
step_count = 1
step_limit = 2
adder = 1
x, y = 0, 0
for n in range(2, inp + 1):
if (step_count <= .5 * step_limit):
x += adder
print(x)
elif (step_count <= step_limit):
y += adder
if (step_count == step_limit):
adder *= -1
step_limit += 2
step_count = 0
step_count += 1
print (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):
inp = prime_c
break
return inp
inp = int(input())
while inp > 0:
temp = primeIndex(int(input()))
spiralSplicer(temp)
inp-=1Also Checkout