Prime Number Algorithm

You need to create an array of booleans as big as the maximum prime number you want to find. At the beginning it's completely initialized to true.

The ith cell of such array will be true if i is a prime number, or false if it's not.

Start iterating from i=2: it's prime, then set to false any cell with an index multiple of 2. Go to the next prime number (i=3) and do the same. Go to the next prime (it's i=5: i=4 is not prime: array[4] was set to false while processing i=2) and do the same again and again.

In my opinion, your algorithm slow because you calculate the inessential number. try this code

int isPrime(int number){

    if(number < 2) return 0;
    if(number == 2) return 1;
    if(number % 2 == 0) return 0;
    for(int i=3; (i*i)<=number; i+=2){
        if(number % i == 0 ) return 0;
    }
    return 1;

}

Here is actually very simple code that use the Sieve of Eratosthenes algorithm. works for all positive int.

int is_prime(int n){
  int p;
  for(p = 2; p < n; p++){
    if(n % p ==0 && p != n)
      return 0;    
  }
  return 1;
}