Take the set of integers
1,2,3,4,5,6,7,8,9,10,11,12,14,15,16,17,18,19,……
First, delete every second number, we get following reduced set.
1,3,5,7,9,11,13,15,17,19,…………
Now, delete every third number, we get
1, 3, 7, 9, 13, 15, 19,….….
Continue this process indefinitely……
Any number that does NOT get deleted due to above process is called “lucky”.
Therefore, set of lucky numbers is 1, 3, 7, 13,………
CODE
bool isLucky(int n)
{
int next_pos = n, counter;
for(counter=2; counter <= next_pos; ++counter)
{
if(next_pos%counter == 0)
return 0;
next_pos -= next_pos/counter;
}
return 1;
}