Menu
Is there any nice algorithm to find the nearest prime number to a given real number? I only need to search within the first 100 primes or so.
At present, I've a bunch of prime numbers stored in an array and I'm checking the difference one number at a time (O(n)?).
955
Input : 16 Output: 17 Explanation: The two nearer prime number of 16 are 13 and 17. But among these, 17 is the closest(As its distance is only 1(17-16) from the given number). Input : 97 Output : 97 Explanation : The closest prime number in this case is the given number number itself as the distance is 0 (97-97).
System. out. println("Nearest Prime Number from "+num+" is "+num2); else//There can be more than 1 nearest prime like for 6 we have 5 and 7 as nearest prime.
Methods to Find Prime Numbers Method 1: Two consecutive numbers which are natural numbers and prime numbers are 2 and 3. Apart from 2 and 3, every prime number can be written in the form of 6n + 1 or 6n – 1, where n is a natural number. Note: These both are the general formula to find the prime numbers.
To prove whether a number is a prime number, first try dividing it by 2, and see if you get a whole number. If you do, it can't be a prime number. If you don't get a whole number, next try dividing it by prime numbers: 3, 5, 7, 11 (9 is divisible by 3) and so on, always dividing by a prime number (see table below).
Rather than a sorted list of primes, given the relatively small range targetted, have an array indexed by all the odd numbers in the range (you know there are no even primes except the special case of 2) and containing the closest prime. Finding the solution becomes O(1) time-wise.
I think the 100th prime is circa 541. an array of 270 [small] ints is all that is needed.
This approach is particularly valid, given the relative high density of primes (in particular relative to odd numbers), in the range below 1,000. (As this affects the size of a binary tree)
133
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
