10650 - Determinate Prime

Difficulty : easy

Solution Description :

Prime number related problem

Read this line carefully "No subset of a series is allowed. For example, a series of five uni-distant primes having even four of them in the interval  is not allowed, all the five primes should be in the interval"

For this problem you can use three array primeNum[](contain all prime number between 1 to 32000), diff[] (contain difference between current prime number and previous prime number), and element[] (contain the number of element at same difference).


1. First pre-generate all prime number from 1 to 32000 and store to array primeNum[].

2. Set difference = current prime number – previous prime number . (i.e. diff[i] = primeNum[i]-primeNum[i-1]).

3. Set element

      A. If (diff[i-1]!=diff[i]) then set element[i]=2

      B. If (diff[i-1]==diff[i]) then set element[i] = element[i-1]+1

4.   For input x and y

Find the start index for x. If primeNum[i]>=x then set start_index = i

For  i=star_index ;  primeNum[i]<=y ; i++

                If element[i]>=3 and element[i+1]!=element[i] and primeNum[i-element[i]+1]>=x

                Then print all prime from primeNum[i-element[i]+1] to primeNum[i].


Remember,  y can be greater than x. If y is greater than x then swap(x,y)


Example:

Prime number between 1 and 20 are

primeNum[1]= 2       diff[1]=2      element[1]=2

primeNum[2]= 3       diff[2]=1      element[2]=2

primeNum[3]= 5       diff[3]=2      element[3]=2

primeNum[4]= 7       diff[4]=2      element[4]=3

primeNum[5]=11       diff[5]=4      element[5]=2

priemNum[6]=13       diff[6]=2      element[6]=2

primeNum[7]=17       diff[7]=4      element[7]=2

primeNum[8]=19       diff[8]=2      element[8]=2

And so on.


a. If x=1 and y=18, then start_index=1  and end_index=7

     Form i=1 to 7 , for i=4 element[4]>=3 so find the lower boundary which 3 (primeNum[4-3+1]) , and 3 is     greater or equal x=2. So, the sequence 3 5 7


     b. If x=18 and y=4, then swap(x,y) after that x=4 and y=18. For that start_index=3 and end_index=7

     Form i=3 to 7 , for i=4 element[4]>=3 so find the lower boundary which 3 (primeNum[4-3+1]) , and 3 is not greater or equal  x=4. So, do not print the sequence.