Need correction of prime number script

[sharath88]

I wrote this script to find whether the given number is prime or not. Logically its correct but it not working so can anyone please find a solution to this problem.

clear
echo "Application to Find if the given number is prime or not"
echo "Enter the number"
read num
prime = `expr $num % 2`
if [ $num -eq 2 ]
then
echo "The given number $num is prime number"
exit
elif [ $prime -eq 1 ]
then
echo "The given number $num is prime number"
else
echo "The given number $num is not a prime number"
fi

Thank you.

[slimx3m]

i recoded your code and here is the correct script.
i am not going to explain it but i hope that it helps you. i think that you could figure out.

let me know if you want me to explain it why your version wasn't working.

#!/bin/bash
clear
echo "Application to Find if the given number is prime or not"
echo "Enter the number"
read num
prime=`expr $num % 2`
if [ $prime -eq 1 ]; then
	echo "The given number $num is not a prime number"
else
	echo "The given number $num is prime number"
fi

[sharath88]

Thank you slimx3m. Yes, Can you please let me know why my version was not working ?

[Rubberman]

The corrected script will show if the number is divisible by two, but neither will determine if the number is prime. You need something to emulate the Sieve of Aristhostenes (a prime number sieve). The algorithm is available in many math text books, as well as math reference books such as "The VNR Concise Enclyclopedia of Mathematics". My copy is well-used and has held a prominent place on my technical book shelf for over 20 years. You also might want to set a limit on the input number as very large numbers that are not divisible by 2 (anything ending in an even number) can take awile to determine whether they are prime.

Hint. The sieve is an algorithm that is well served by a recursive process. With a 100 number starting segment, a number up to 100,000,000 will only take 2 recursions. 10,000,000,000,000,000 (16 digits) only 3. FYI, that is about the limit of a double-precision floating point number. A 64 bit unsigned integer can handle up to between 18 and 19 digits. For numbers bigger than that you will need an unlimited precision math package, which are a lot slower than native integers. Extended 80 bit precision on the x86/x87 processor can allow up to 23-24 digits, but it requires specialized programming to directly access the math co-processor unit of the Pentium chip.

[Thrillhouse]

The problem was with this line:

prime = `expr $num % 2`

Bash doesn't like those spaces.

Neither of these scripts will tell you if a given number is prime or not, though. They really only tell you if the number is odd or even. There is no definitive algorithm for determining primes (yet). If there was, much of the cryptography that's used today would be obsolete. However, there are more complicated algorithms for determining the primality of a number including Fermat's test and the more robust Miller-Rabin test.

[slimx3m]

sharath88,
i guessed that your question has been answered pretty well by rubberman and thrillhouse.

[Rubberman]

The problem was with this line:

prime = `expr $num % 2`

Bash doesn't like those spaces.

Neither of these scripts will tell you if a given number is prime or not, though. They really only tell you if the number is odd or even. There is no definitive algorithm for determining primes (yet). If there was, much of the cryptography that's used today would be obsolete. However, there are more complicated algorithms for determining the primality of a number including Fermat's test and the more robust Miller-Rabin test.

Actually, determining if a number is prime or not isn't difficult. However, the time to determine it goes up logarithmically with the length of the number, which is one reason why public key encryption algorithms use keys upwards of 1024 digits (not bits). The other reason why it is hard to break PKI encrypted data is that they key is a the product of two 1024+ digit prime numbers, and factorizing such numbers is even harder than determining if the number is prime or not. However, the Sieve of Eratosthenes (I misspelled it below) will determine if a specific number is prime fairly efficiently, and accurately. There are other, more modern algorithms as well, especially for factoring large numbers into their prime factors, which is what is required for breaking PKI encryption. An old such algorithm is called Euclid's algorithm, which given that Euclid discovered it, is quite old! Both of these fellows were ancient Greek mathematicians, though not quite contemporaries. Euclid lived around 300 B.C. and Eratosthenes around 275-200 B.C. (give or take). So, they had a handle on this stuff well over 2000 years ago!

[Thrillhouse]

Actually, determining if a number is prime or not isn't difficult. However, the time to determine it goes up logarithmically with the length of the number

For large numbers, primality tests can only tell you if a number is probably prime, depending on the degree of certainty you need. There still exists composite numbers that can pass any primality test, Carmichael numbers in the case of Fermat's test. For this script, the algorithm chosen (besides mod'ing by 2) to determine primality is trivial considering the largest number that will fit inside of a primitive int is very small in the cryptographic sense. But that was really besides the point.

The other reason why it is hard to break PKI encrypted data is that they key is a the product of two 1024+ digit prime numbers, and factorizing such numbers is even harder than determining if the number is prime or not.

This is true for RSA but not all public key encryption algorithms.

However, the Sieve of Eratosthenes (I misspelled it below) will determine if a specific number is prime fairly efficiently, and accurately. There are other, more modern algorithms as well, especially for factoring large numbers into their prime factors, which is what is required for breaking PKI encryption. An old such algorithm is called Euclid's algorithm, which given that Euclid discovered it, is quite old! Both of these fellows were ancient Greek mathematicians, though not quite contemporaries. Euclid lived around 300 B.C. and Eratosthenes around 275-200 B.C. (give or take). So, they had a handle on this stuff well over 2000 years ago!

None of the algorithms (to date) for factoring large numbers into their prime composites are fast enough for very large numbers. If you were to use Euclid (or even Extended Euclid) to crack a 1024-bit RSA key, you would be waiting for a very long time. But if you can predict the distribution of primes (i.e. prove the Riemann Hypothesis) then it doesn't matter which integer factorization algorithm you choose. But this is all beyond the scope of the original poster's question.

[Rubberman]

So, in the final analysis (if there ever is one), sharath88 needs to incorporate something more than determining non-divisibility by two for this script. It is certainly possible, and building or hard-coding a 100 cell segment for a sieve would enable him to have a reasonable prime number detection tool for smallish numbers (up to 100M).

[sharath88]

Thank you all for your answer. I understood the problem.