Problems with program for prime numbers

Hey guys…
I made a program which will run from an initial number to a final number (given by user using serial monitor) using a for loop, searching for prime numbers(for which i made a function). Whenever a number is prime, a green led(pin 11) will blink and that prime number will show in the serial monitor. For the non-prime numbers, a red led(pin 12) will glow. The problems are:

  1. If i enter the initial and final values with some time gap (say more than 2 seconds) in the serial monitor, the program does not execute at all.

  2. For relatively small values, say less than 1000, the program will run smoothly, but if i enter large values like >5000, at the end, the program becomes very slow…(I tried for values like 1,00,000 to 2,00,000 and the led blinked only once every one or two seconds…)

  3. The function displayAtEnd() does not seem to work

Here’s the code:

void setup() {
pinMode(11,OUTPUT);
pinMode(12,OUTPUT);

Serial.begin(9600);

}
long i;
long prime(long x) //PRIME FUNCTION
{
int t=0;
for (long i=1;i<=x;i++)
{
if ( x%i==0)
t++;
}
if (t==2)
{

digitalWrite(11,HIGH);
delay(10);
digitalWrite(11,LOW);
delay(10);

Serial.println(x);

}
else{
digitalWrite(12,HIGH);
delay(10);
digitalWrite(12,LOW);
delay(10);}

}
long initial,final;
void loop() {

if (Serial.available())
{
initial=Serial.parseInt();
final=Serial.parseInt();

long prime(long x); //CALLING THE PRIME FUNCTION
for (long i=initial;i<=final;i++)
{
prime(i); //THE PRIME FUNCTION OPERATES ON ALL THE VALUES
//IN THE RANGE SPECIFIED BY THE USER
}
}

digitalWrite(11,LOW);
digitalWrite(12,LOW);
void displayAtEnd(); //CALLING THE displatAtEnd() FUNCTION(problem)

}
void displayAtEnd(){Serial.print("THESE ARE ALL THE PRIME NUMBERS BETWEEN “); //displayAtEnd()
// function
Serial.print(initial);
Serial.print(” AND ");
Serial.print(final);
}

  long prime(long x);                              //CALLING THE PRIME FUNCTION

Comment and code don't match. Guess which one the compiler uses?

 void displayAtEnd();                               //CALLING THE displatAtEnd() FUNCTION(problem)

Ditto.

Don't forget to use code tags when posting code.

arjmon: 1. If i enter the initial and final values with some time gap (say more than 2 seconds) in the serial monitor, the program does not execute at all.

if (Serial.available())
  {
  initial=Serial.parseInt();
  final=Serial.parseInt();

Well, you wait about 62 nanoseconds between reading in the first number and the second number. That doesn't give the user very much time does it? If you're quick, then they'll both be there by the time you get to the Serial.available(). But if you're not quick and only the first number has been input by that time then it reads and gets the first number but when you make the second parseInt call there's nothing there to get.

You could make the loop so that it is checking for the first number until it gets it, and then it checks for the second number until it gets it, and only if it has both numbers does it enter the rest of the code. You need a couple of boolean variables to keep up with what has been enetered and a few if statements to decide which section of code to run on each pass of the loop.

arjmon: 2. For relatively small values, say less than 1000, the program will run smoothly, but if i enter large values like >5000, at the end, the program becomes very slow...(I tried for values like 1,00,000 to 2,00,000 and the led blinked only once every one or two seconds...)

Well, if I handed you a piece of paper and asked you to divide 100 by every number less than 100, and then asked you on a second sheet to divide 5000 by every number less than 5000 don't you think the second assignment would take significantly longer to do?

You should think about your algorithm a little. Why test 1? You know everything is divisible by 1. Why check any factor larger than the square root of the number you are testing? If you want to know if 100 is prime, you don't need to test any factors larger than 10. If there was a factor larger than 10 (like 50) then it would have to be paired with a factor smaller than 10 (in the case of 50 it would be 2). You only need to find one of those to know that it isn't prime.

Lastly, it would make a lot more sense to keep up with a list of the primes you've found so far and only test against those. If a value you are testing is not divisible by 2, then there is no reason to test it against 4 is there? You only need to try to divide by the prime numbers, if any other non-prime number is a factor then there is necessarily a prime factor smaller than it. Again you only need to find one to prove it isn't prime.

arjmon:
2. For relatively small values, say less than 1000, the program will run smoothly, but if i enter large values like >5000, at the end, the program becomes very slow…(I tried for values like 1,00,000 to 2,00,000 and the led blinked only once every one or two seconds…)

That’s perhaps the slowest prime number algorithm I ever saw.

What about this as a first step of speeding up calculations:

  boolean isPrime=true;
  for (long i=2;i<x;i++)
  {
    if ( x%i==0)
    {
       isPrime=false;
       break;
    }
  }
  if (isPrime)
....

http://en.wikipedia.org/w/index.php?title=Primality_test#Java_implementation

Thanks guys... Well the program does it's work, I agree that I should use the tips that you gave me to make it faster... Yes, the program is very slow as I have come to realise now... I will improve it... Thanks

Hi, As jurs points out you only need to test odd numbers, evens cannot be primes for obvious reasons, apart from 2.

Tom..... :)