0
There are several methods; the most efficient ones are quite complicated. Here are the simplest methods:1) Try dividing the candidate for Prime number, which I shall call "n", by all numbers from 2 to n-1. For instance, to check whether 7 is a prime number, check divisibility by 2, 3, 4, 5, 6. Since it isn't divisible by any of those, it is a prime number.
2) Same as above, but use some optimizations. First, only divide by 2, and then by odd numbers. Second, only do the division by numbers up the the square root of your number "n". To check whether 101 is a prime number, try dividing by 2, 3, 5, 7, and 9. Dividing by 11, and larger numbers, is no longer necessary, since 11 is larger than the square root of 101.
(Why the square root? - If your number "n" is divisible by some number that is LARGER than its square root, it will be the product of this number and another factor that is SMALLER than the square root - and you would already have found this factor previously.)
The second method can be used conveniently for numbers up to a few thousand or so. If you write a computer program, you can easily use it to check primality of millions or even billions.
There are other methods, which are both more efficient (and therefore appropriate for much larger numbers), and more complicated. Some will determine that a number is "probably a prime" - which is good enough for many purposes, such as cryptography (the probability of a false positive can be made very, very small). There are other methods with which you can know for sure whether a number is prime.
If you are interested in the gory details, you might check the Wikipedia article on "Primality test" - or search for other sources.
Still curious? Ask our experts.
Chat with our AI personalities
Devin
Maxine
Beau
Add your answer:
Earn +20 pts
Write an algorithm to check whether a number is a prime number or not?
You can write out this algorithm. This will then be programmed into the device to make determining prime numbers easier.
What is prime factortization?
Prime factorization is the process of determining all of the prime factors of a given number. Prime factors are the prime numbers that when multiplied together give you the number to be factored. For example the prime factorization of 30 is 15 x 2
Is 743235 prime or composite?
A good way to instantly tell if a number is prime or composite is to learn some tricks to tell if a number divides by certain numbers. For instance, if a number is even, we know it is composite as it must be divisible by 2. If a number ends in 0 or 5, then it also cannot be prime as it would be divisible by 5. In this case, the number ends in 5, so we can tell it must be composite and cannot be prime.
What is the greatest prime that must be used to determine if 2089 is prime?
43 is the greatest prime that needs to be used in determining if 2089 is prime.
Do you prefer to calculate the gcf of two numbers by listing factors or by determining the prime factorzation explain your awnser?
Determining the prime factorization. It's faster and more efficient with larger numbers.
