Logo Questions Linux Laravel Mysql Ubuntu Git Menu
HTML CSS JAVASCRIPT SQL PYTHON PHP BOOTSTRAP JAVA JQUERY R React Kotlin
 

Is there a simple algorithm that can determine if X is prime?

Tags:

algorithm

primes

I have been trying to work my way through Project Euler, and have noticed a handful of problems ask for you to determine a prime number as part of it.

  1. I know I can just divide x by 2, 3, 4, 5, ..., square root of X and if I get to the square root, I can (safely) assume that the number is prime. Unfortunately this solution seems quite klunky.

  2. I've looked into better algorithms on how to determine if a number is prime, but get confused fast.

Is there a simple algorithm that can determine if X is prime, and not confuse a mere mortal programmer?

Thanks much!

like image 357
Pulsehead Avatar asked Oct 09 '08 18:10

Pulsehead

People also ask

How do you know if X is prime?

The simplest primality test is trial division: given an input number, n, check whether it is evenly divisible by any prime number between 2 and √n (i.e. that the division leaves no remainder). If so, then n is composite. Otherwise, it is prime.

What's the best algorithm to check if a number is prime?

Most algorithms for finding prime numbers use a method called prime sieves. Generating prime numbers is different from determining if a given number is a prime or not. For that, we can use a primality test such as Fermat primality test or Miller-Rabin method.

Is there an easy way to tell if a number is prime?

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).

What is an algorithm used to find primes?

In mathematics, the sieve of Eratosthenes is an ancient algorithm for finding all prime numbers up to any given limit.

1 Answers

The first algorithm is quite good and used a lot on Project Euler. If you know the maximum number that you want you can also research Eratosthenes's sieve.

If you maintain the list of primes you can also refine the first algo to divide only with primes until the square root of the number.

With these two algoritms (dividing and the sieve) you should be able to solve the problems.

Edit: fixed name as noted in comments

like image 155
rslite Avatar answered Sep 19 '22 16:09

rslite
Sign in to Comment

Related questions

What are the real-world applications of huffman coding?
Cheap algorithm to find measure of angle between vectors
Is there a better way to guess possible unknown variables without brute force than I am doing? Machine learning? [duplicate]
Efficiently find an integer not in a set of size 40, 400, or 4000
Why is std::rotate so fast?
Best way to determine if a sequence is in another sequence?
Fastest algorithm to check if a number is pandigital?
Time complexity of a recursive algorithm
Find local minimum in n x n matrix in O(n) time
LRU implementation in production code
How to find all taxicab numbers less than N?
Is there an overview of the most common algorithms?
Fastest way to generate binomial coefficients
How can std::make_heap be implemented while making at most 3N comparisons?
Big O - O(log(n)) code example
Finding two non-subsequent elements in array which sum is minimal
Round to the nearest power of two
selection based on percentage weighting
What is the Most Efficient way to compare large List of integers to smaller List of integers?
Create non-intersecting polygon passing through all given points

Donate For Us

If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!