There are some problems: Why do you print out count when it didn’t divide by x? It doesn’t mean it’s prime, it means only that this particular x doesn’t divide it continue moves to the next loop iteration – but you really want to stop it using break Here’s your code with a few fixes, … Read more
var number; Console.WriteLine(“Accept number:”); number = Convert.ToInt32(Console.ReadLine()); if (IsPrime(number)) { Console.WriteLine(“It is prime”); } else { Console.WriteLine(“It is not prime”); } public static bool IsPrime(int number) { if (number <= 1) return false; if (number == 2) return true; if (number % 2 == 0) return false; var boundary = (int)Math.Floor(Math.Sqrt(number)); for (int i = … Read more
The fastest algorithm for general prime testing is AKS. The Wikipedia article describes it at lengths and links to the original paper. If you want to find big numbers, look into primes that have special forms like Mersenne primes. The algorithm I usually implement (easy to understand and code) is as follows (in Python): def … Read more
Of many prime number tests floating around the Internet, consider the following Python function: def is_prime(n): if n == 2 or n == 3: return True if n < 2 or n%2 == 0: return False if n < 9: return True if n%3 == 0: return False r = int(n**0.5) # since all primes … Read more
I recommend using 92821. Here’s why. To give a meaningful answer to this you have to know something about the possible values of i and j. The only thing I can think of in general is, that in many cases small values will be more common than large values. (The odds of 15 appearing as … Read more
Build bipartite graph structure – connect a[i] with all its divisors from b[]. Then find maximum matching and check whether it is perfect matching (number of edges in matching is equal to the number of pairs (if graph is directed) or to doubled number). Arbitrary chosen Kuhn algorithm implementation here. Upd: @Eric Duminil made great … Read more
I think the article explains it rather well, but I’ll try my hand at it as well. Input is in unary form. 1 is 1, 2 is 11, 3 is 111, etc. Zero is an empty string. The first part of the regex matches 0 and 1 as non-prime. The second is where the magic … Read more
“If I have seen further…” The erat2 function from the cookbook can be further sped up (by about 20-25%): erat2a import itertools as it def erat2a( ): D = { } yield 2 for q in it.islice(it.count(3), 0, None, 2): p = D.pop(q, None) if p is None: D[q*q] = q yield q else: # … Read more
About a year ago I was working this area for libc++ while implementing the unordered (hash) containers for C++11. I thought I would share my experiences here. This experience supports marcog’s accepted answer for a reasonable definition of “brute force”. That means that even a simple brute force will be fast enough in most circumstances, … Read more
OK, so forget about C. Suppose I give you a number and ask you to determine if it’s prime. How do you do it? Write down the steps clearly, then worry about translating them into code. Once you have the algorithm determined, it will be much easier for you to figure out how to write … Read more