ALICESIE - Alice Sieve

no tags 

Alice has recently learned to use the Sieve of Eratosthenes, an ancient algorithm for finding all prime numbers up to any given limit. As expected, she was really impressed by it's simplicity and elegancy.

Now, she has decided to design her own sieve method: The Sieve of Alice, formally defined by the following procedure, which determines the Sieve of Alice up to a given limit N.

  1. Create a list of consecutive integers from N to 2 (N, N-1, N-2, ..., 3, 2). All of those N-1numbers are initially unmarked.
  2. Initially, let P equal N, and leave this number unmarked.
  3. Mark all the proper divisors of P (i.e. P remains unmarked).
  4. Find the largest unmarked number from 2 to P – 1, and now let P equal this number.
  5. If there were no more unmarked numbers in the list, stop. Otherwise, repeat from step 3.

Unfortunately, Alice has not found an useful application for it's Sieve. But she still wants to know, for a given limit N, how many integers will remain unmarked.


The first line contains an integer T, the number of test cases (1 ≤ T ≤ 10^4) . Each of the next T lines contains an integer N (2 ≤ N ≤ 10^6).


Output T lines, one for each test case, containing the required answer.




hide comments
Arka Roy: 2017-08-18 11:28:46

that feeling when you get the logic of a good question and question like this fools you !! :p this question is a reminder to think simple

hunnychauhan: 2017-07-18 13:59:45

just observe the pattern...

hassanarif63: 2017-07-03 07:47:58


kooljais24: 2017-06-19 17:19:27

lt's too much easy..O(1)...just observe the results

Last edit: 2017-06-19 17:20:25
jainsahil1997: 2017-05-19 07:11:48

Fooled here :-P

giorgosgiapis: 2017-04-05 13:02:07

Easy one. O(1) per test case!

nilabja16180: 2017-03-05 20:54:20

Just LOL! question!

aaditya111: 2017-02-24 11:51:44

Tooooooo........ simple , guyz apply engineers mind nd win d race, this question has already made u fool ha ha ha ha ha ......LOL

Last edit: 2017-02-24 11:52:19
gauravgb21: 2017-02-19 15:18:26

ohh my god!! i haven't seen a problem like this!! learned a lot!!LOL!!

awesomeabhinav: 2016-12-24 13:59:32

shit man, this question fooled me

Added by:Paulo Costa
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64