3 ms·

I don't really see the point in prime classification, I feel like you're never gonna get better than doing a deterministic sieve algorithm. Even if it did do qu

I don't really see the point in prime classification, I feel like you're never gonna get better than doing a deterministic sieve algorithm. Even if it did do quite well in terms of accuracy, probabilistic models aren't 100% correct so you still have to check for primality deterministically. However the twin prime factorizer idea was interesting and could potentially lead to some factorization speedups (based on heuristics) if done correctly. Either way though, prime number distribution is quite tricky - we should probably be looking in other number bases as well rather than just base 10.

reubenmorais 9y ago
> Even if it did do quite well in terms of accuracy, probabilistic models aren't 100% correct so you still have to check for primality deterministically. Deterministic primality tests are rarely used in practice -- they're too slow, and the probabilistic tests have such a high accuracy that it doesn't matter.
hulahoof 9y ago
Either way though, prime number distribution is quite tricky - we should probably be looking in other number bases as well rather than just base 10. This interested me so I went looking for how primes would work in other bases, this answer implies that primes are the same regardless of base: A prime is a prime no matter which base you use to represent it. On the surface one might think that in Hex you would have 35 = 15 as "usual," but it really turns out that 35 = F. The example 21 doesn't work too well because it is not prime. The base ten number 37 is better, because it is prime, but its Hex representation is 25, which sort of looks non-prime. Hex 25 is not, however, repeat not, 5 squared. Okay, enough for examples. The fact of being prime or composite is just a property of the number itself, regardless of the way you write it. 15 and F and Roman numeral XV all mean the number, which is 3 times 5, so it is composite. That is the way it is for all numbers, in the sense that if a base ten number N has factors, you can represent those factors in Hex and their product will be the number N in Hex. Relating to your question about base 13, the base ten number 13 will be represented as "10" in that system, but "10" will still be a prime, because you cannot find two numbers other than 1 and "10" that will multiply together to make "10". I hope this helps you think about primes in other bases. [1] http://mathforum.org/library/drmath/view/55880.html http://mathforum.org/library/drmath/view/55880.html
- rahimnathwani 9y ago
  "this answer implies that primes are the same regardless of base" Right. If you have some quantity of apples, then can you lay them out in a regular rectangular-shaped grid (more than 1 apple wide)? If not, the quantity is prime. You can count the apples in any base you like.
  - peteretep 9y ago
    This is the far more intuitive answer I use when explaining to people.

reubenmorais 9y ago

> Even if it did do quite well in terms of accuracy, probabilistic models aren't 100% correct so you still have to check for primality deterministically. Deterministic primality tests are rarely used in practice -- they're too slow, and the probabilistic tests have such a high accuracy that it doesn't matter.

hulahoof 9y ago

Either way though, prime number distribution is quite tricky - we should probably be looking in other number bases as well rather than just base 10. This interested me so I went looking for how primes would work in other bases, this answer implies that primes are the same regardless of base: A prime is a prime no matter which base you use to represent it. On the surface one might think that in Hex you would have 35 = 15 as "usual," but it really turns out that 35 = F. The example 21 doesn't work too well because it is not prime. The base ten number 37 is better, because it is prime, but its Hex representation is 25, which sort of looks non-prime. Hex 25 is not, however, repeat not, 5 squared. Okay, enough for examples. The fact of being prime or composite is just a property of the number itself, regardless of the way you write it. 15 and F and Roman numeral XV all mean the number, which is 3 times 5, so it is composite. That is the way it is for all numbers, in the sense that if a base ten number N has factors, you can represent those factors in Hex and their product will be the number N in Hex. Relating to your question about base 13, the base ten number 13 will be represented as "10" in that system, but "10" will still be a prime, because you cannot find two numbers other than 1 and "10" that will multiply together to make "10". I hope this helps you think about primes in other bases. [1] http://mathforum.org/library/drmath/view/55880.html http://mathforum.org/library/drmath/view/55880.html

rahimnathwani 9y ago
"this answer implies that primes are the same regardless of base" Right. If you have some quantity of apples, then can you lay them out in a regular rectangular-shaped grid (more than 1 apple wide)? If not, the quantity is prime. You can count the apples in any base you like.
- peteretep 9y ago
  This is the far more intuitive answer I use when explaining to people.