CODEWITHSUNDEEP
c++algorithm
NoPlaceLike127.0.0.1
NoPlaceLike127.0.0.1

Reputation: 21

What are the advantages and disadvantages of this algorithm used to determine if a number is prime?

Here is my code. I am primarily wanting to know how this compares to other algorithms in terms of speed and memory.

#include <iostream>
using namespace std;

bool isPrime(int input){
    for(int i = 2; i <= input; i++)
        if(input%i == 0 && i < input)
            return false;
    return true;
}

int main(){
    int input;
    cin >> input;
    cout << isPrime(input);
}

Upvotes: 0

Views: 291

Answers (3)

rcgldr
rcgldr

Reputation: 28826

You could try something like this (not sure if I checked all possible cases). To avoid a potential overflow issue, i <= (input/i) is used instead of (i*i) <= input.

bool isPrime(int input){
int i;
    if(input%2 == 0)
        return false;
    for(i = 3; i <= (input/i); i += 2)
        if(input%i == 0)
            return false;
    return true;
}

Upvotes: 0

Weather Vane
Weather Vane

Reputation: 34585

For one thing you need to be trying odd numbers and stepping by 2, because none of the even candidates (except 2) is itself prime. For another your loop needs to terminate at i <= input / 3 for the same reason. I have increased your execution speed sixfold.

bool isPrime(int input){
    int endval = input / 3;
    if (input <= 2) 
       return true;
    if ((input & 1) == 0)
       return false;
    for( int i = 3; i <= endval; i+=2)
        if(input%i == 0)
            return false;
    return true;
}

Upvotes: 2

Zeta
Zeta

Reputation: 105886

First of all, your algorithm takes linear time, O(n). You can speed it up tremendously if you check only the numbers up to sqrt(n): (i * i <= n). That being said, if you want to check k numbers of size ~n for being prime, you would end up with O(k sqrt (n)). That's still bad.

In this case, you would built a sieve (Atkins or Eratosthenes), which can be implemented in O(n log log n) for numbers up to n. This way, every following test can be done in O(1).

Upvotes: 6

Related Questions