Taking your example, N=2^4*6397*179717. Using the totient function: 1800598484394*(1/2)*(6396/6397)*(179716/179717)≈900153495714.

So, basically, the totient function does work, but don't use it to be very accurate.

]]>i am not sure if this equation can come in handy... maybe it could

(Fermat's little theorem)

it takes a couple of days to find them.. I think we can use smthing like the totient function but I'm not sure

for example: if n = 2, q=10 there are (10/2) numbers divided by 2, so 10 - 5 = 5 numbers that don't divide by 2

but if n = 2*3 the thing get a little bit complicated. acording to the totient function there will be

10*(1/2)*(2/3)=3.(3) the result is not integer here is the problem.. when should we consider x.(6) is x+1 and when should we consider x.(6) is 6?

I hope you understand me.

]]>Find all primes less than Q (using your example 2,3,5,7,11,13)

Find the prime factors of N (using your example 2,2,3)

Exclude the N-list from the Q-list: 5,7,11,13

Is that it?

(BTW: we have a tool to find prime factors here)

]]>N = 12, Q = 14

the numbers I'm looking for are 1,5,7,11,13 (these numbers have no common divisors with N and are smaller then Q)

the first step in solving the problem is indeed to find out the prime numbers that divide N.. but after that?]]>

I have a program written in ".net" that calculates primes. I made a list of about 100,000 once but never did anything with it. I was thinking of making a million of them and putting them on the website somehow.

Anyway, my program could be adapted to solve your problem I should think.

]]>I think there are a few proofs that can give limits to your question as in there are at least x number of primes beween 2 and N that are less than or equal to Q. But I am not sure if that is what you are asking.

There are exactly 25 primes less than 100 about %25 of all numbers from 1-100 are prime.

```
2 3 5 7 11
13 17 19 23 29
31 37 41 43 47
53 59 61 67 71
73 79 83 89 97
```