Discussion about math, puzzles, games and fun. Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ ¹ ² ³ °
 

You are not logged in. #1 20050803 05:16:17
prime numbershow do I find out how many numbers that have no common divisors with N and are smaller or equal to Q are there? #2 20050803 06:16:32
Re: prime numbersThe 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 bruteforce all inclusive method and have never really needed to calulate primes greater than 50 digits. Code: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 #3 20050803 07:42:47
Re: prime numbersThe only way I can think of is, like eleusis said, a program. "The physicists defer only to mathematicians, and the mathematicians defer only to God ..."  Leon M. Lederman #4 20050803 16:14:43
Re: prime numbersfor example: #5 20050803 16:43:28
Re: prime numbersSo, the problem may be approached this way: "The physicists defer only to mathematicians, and the mathematicians defer only to God ..."  Leon M. Lederman #6 20050803 18:11:55
Re: prime numberssay Q = 1800598484394 and N = 18394394384 #8 20050805 01:30:48
Re: prime numbersI'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. Why did the vector cross the road? It wanted to be normal. 