prime numbers

adrian · 2005-08-02 07:16:17

how do I find out how many numbers that have no common divisors with N and are smaller or equal to Q are there?

eleusis · 2005-08-02 08:16:32

The best primality test that I know is a small program that tests all numbers less than or equal to √x where x is the prime number that you are looking for. When you start testing numbers over 200 digits long then you start to run into the problem of finding a solution in this lifetime. There are other methods for finding prime numbers, like counting by primes to cut down on cycles, but I trust the brute-force all inclusive method and have never really needed to calulate primes greater than 50 digits.

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

MathsIsFun · 2005-08-02 09:42:47

The only way I can think of is, like eleusis said, a program.

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.

adrian · 2005-08-02 18:14:43

for example:
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?

MathsIsFun · 2005-08-02 18:43:28

So, the problem may be approached this way:

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)

adrian · 2005-08-02 20:11:55

say Q = 1800598484394 and N = 18394394384
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.

wcy · 2005-08-04 01:10:38

a^p=a (mod p)

i am not sure if this equation can come in handy... maybe it could
(Fermat's little theorem)

mathsyperson · 2005-08-04 03:30:48

I've never heard of the totient function before, but it seems like it's meant to be used to find an estimate. I think it takes the prime factors of N, divides does 1-(1/p) for each of them and multiplies all of those values together. That would give the proportion of all numbers that don't share factors with N, and so then you would multiply that value by Q to get the number of numbers less than or equal to Q that fits that description. It's only an estimate because the numbers are irregularly distributed when there is more than one prime factor. e.g N=12, Q=14, xxxx5x7xxx11x13x. However, when dealing with big numbers such as the ones you have given, the inaccuracy is much less.

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.

Math Is Fun Forum

#1 2005-08-02 07:16:17

prime numbers

#2 2005-08-02 08:16:32

Re: prime numbers

#3 2005-08-02 09:42:47

Re: prime numbers

#4 2005-08-02 18:14:43

Re: prime numbers

#5 2005-08-02 18:43:28

Re: prime numbers

#6 2005-08-02 20:11:55

Re: prime numbers

#7 2005-08-04 01:10:38

Re: prime numbers

#8 2005-08-04 03:30:48

Re: prime numbers

Board footer