My Blog List

Tuesday, July 19, 2016

PrimePrime count sieve of Eratosthenes.

this problem is from codefights.
https://codefights.com/challenge/doXskkj8PMAJ27Epk/main

try to find prime numbers by using  sieve of Eratosthenes.
and count luckyprimeprime.

I think this is not difficult though.

 int c, t, s, i;
 int luckyandprimeprime(int l, int r) {
  int[] p = new int[100001];
  
  s = p.length;
  for ( i = 2; i < s; i++, t=0) 
   while ((t += i) < s) 
    p[t]++;   

  for (i = 0; i < l; i++)
   if (p[i] == 1)
    c++;

  for (i = l; i <= r; i++) {
   if (p[i] == 1)
    c++;

   if (p[c] == 1)
    t++;
  }
  return t;
 }

Recently Lucky learnt how to check if the given number is prime or not. Bunny, Lucky's friend, decided to give her a task to test her skills.
Let's call number P Prime Prime if the number of prime numbers in the range [1, P] is prime. Bunny asked Lucky to calculate the number of Prime Prime numbers in the range [l, r]. Can you you help her?
Example
For l = 1 and r = 10, the output should be
luckyandprimeprime(l, r) = 4.
There're 4 prime numbers in the given range: 235 and 7. Thus, Prime Prime numbers are 345and 64 numbers altogether.
Input/Output
  • [time limit] 3000ms (java)
  • [input] integer l
    Constraints:
    1 ≤ l ≤ r.
  • [input] integer r
    Constraints:
    l ≤ r ≤ 105.
  • [output] integer
    The number of Prime Prime numbers in the range [l, r].




Recently Lucky learnt how to check if the given number is prime or not. Bunny, Lucky's friend, decided to give her a task to test her skills.
Let's call number P Prime Prime if the number of prime numbers in the range [1, P] is prime. Bunny asked Lucky to calculate the number of Prime Prime numbers in the range [l, r]. Can you you help her?
Example
For l = 1 and r = 10, the output should be
luckyandprimeprime(l, r) = 4.
There're 4 prime numbers in the given range: 235 and 7. Thus, Prime Prime numbers are 345and 64 numbers altogether.
Input/Output
  • [time limit] 3000ms (java)
  • [input] integer l
    Constraints:
    1 ≤ l ≤ r.
  • [input] integer r
    Constraints:
    l ≤ r ≤ 105.
  • [output] integer
    The number of Prime Prime numbers in the range [l, r].

No comments:

Post a Comment