//author- Bhuvnesh Jain
//complexity- O(m*(n^1/2))
#include <stdio.h>
#include <math.h>
int main()
{
int i, j, n, m, x, y, count=0;
int arr[m+1];
for (i=1; i<=m; i++)
arr[i] = 0;
if (n%2==0)
{
//marking multiples of 2 similar to sieving
for (i=2; i<=m; i+=2)
arr[i] = 1;
//factorising n
while (n%2==0)
n/=2;
}
for (i=3; i<=x; i+=2)
{
if (n%i==0)
{
//marking multiples of i similar to sieving
for (j=i; j<=m; j+=i)
arr[j] = 1;
//factorising n
while (n%i==0)
n/=i;
}
}
printf("The list of numbers is:\n"); for (i=1; i<=m; i++)
{
if (arr[i]==0)
{
count++;
}
}
printf("\nCount = %d\n", count
); return 0;
}
Ly9hdXRob3ItIEJodXZuZXNoIEphaW4KCi8vY29tcGxleGl0eS0gTyhtKihuXjEvMikpCgojaW5jbHVkZSA8c3RkaW8uaD4KI2luY2x1ZGUgPG1hdGguaD4KCmludCBtYWluKCkKewogICAgaW50IGksIGosIG4sIG0sIHgsIHksIGNvdW50PTA7CiAgICBzY2FuZigiJWQgJWQiLCAmbiwgJm0pOwogICAgaW50IGFyclttKzFdOwogICAgZm9yIChpPTE7IGk8PW07IGkrKykKICAgICAgICBhcnJbaV0gPSAwOwogICAgaWYgKG4lMj09MCkKICAgIHsKICAgICAgICAvL21hcmtpbmcgbXVsdGlwbGVzIG9mIDIgc2ltaWxhciB0byBzaWV2aW5nCiAgICAgICAgZm9yIChpPTI7IGk8PW07IGkrPTIpCiAgICAgICAgICAgIGFycltpXSA9IDE7CiAgICAgICAgLy9mYWN0b3Jpc2luZyBuCiAgICAgICAgd2hpbGUgKG4lMj09MCkKICAgICAgICAgICAgbi89MjsKICAgIH0KICAgIHggPSBzcXJ0KG4pOwogICAgZm9yIChpPTM7IGk8PXg7IGkrPTIpCiAgICB7CiAgICAgICAgaWYgKG4laT09MCkKICAgICAgICB7CiAgICAgICAgICAgIC8vbWFya2luZyBtdWx0aXBsZXMgb2YgaSBzaW1pbGFyIHRvIHNpZXZpbmcKICAgICAgICAgICAgZm9yIChqPWk7IGo8PW07IGorPWkpCiAgICAgICAgICAgICAgICBhcnJbal0gPSAxOwogICAgICAgICAgICAvL2ZhY3RvcmlzaW5nIG4KICAgICAgICAgICAgd2hpbGUgKG4laT09MCkKICAgICAgICAgICAgICAgIG4vPWk7CiAgICAgICAgfQogICAgfQogICAgcHJpbnRmKCJUaGUgbGlzdCBvZiBudW1iZXJzIGlzOlxuIik7CiAgICBmb3IgKGk9MTsgaTw9bTsgaSsrKQogICAgewogICAgICAgIGlmIChhcnJbaV09PTApCiAgICAgICAgewogICAgICAgICAgICBjb3VudCsrOwogICAgICAgICAgICBwcmludGYoIiVkXG4iLCBpKTsKICAgICAgICB9CiAgICB9CiAgICBwcmludGYoIlxuQ291bnQgPSAlZFxuIiwgY291bnQpOwogICAgcmV0dXJuIDA7Cn0=