2021 isn't a prime number, it's something much worse: it's the product of two prime factors that are as large as they can be, so it takes as long as possible to find out it's not prime. I'm calling this class "fucker numbers"
regret to inform fucker numbers are already in the OEIS under the mundanely informative name "products of two successive primes" https://oeis.org/A006094
@Ricardus yeah, imagine you're trying to check if it's prime, so you try dividing by 2, 3, ... etc, and you don't get a prime factor until the last possible prime the smallest prime factor could be (the greatest prime less than the square root)
@IceWolf basically the smallest of the two prime factors is the largest prime that's less than the number's square root, so if you were primality checking naively by dividing by 2, 3, ..., it would take as long as possible to find a factor
@tomharris sorry if this is an unwelcome question, but would you mind clarifying what makes the prime factors “as large as they can be”?
@Ethancdavenport the smallest prime factor is the largest prime less than the number’s square root. so if you are primarity checking naively it takes as long as possible to find a factor
@tomharris though there is a class of attacks on RSA if the primes are too close together. For real RSA primes not having the primes on the same order of magnitude is ideal.
Server run by the main developers of the project It is not focused on any particular niche interest - everyone is welcome as long as you follow our code of conduct!