Primality testing

[closed account 4wbR92yv]

Recall that a prime number is one that is only divisible by itself and one. By definition, 2 is the only even prime.

A naive algorithm for testing whether a number is prime is to implement the definition directly; test whether the number is divisible by any number other than 1 or itself.

This approach is somewhat wasteful, though; in reality, you can check fewer numbers than this. Hint: What is the largest possible factor of a given number? You may find the function std::floor(), defined in <cmath>, to be useful.

Complete the function is_prime() below. You may use any code you've written for earlier questions.

#include <iostream>
#include <cmath>

/* 
   takes one argument, an int x.
   returns true if and only if s is prime, false otherwise
*/

bool is_prime(int x) {

}

int main() {
  int query;
  std::cin >> query;
  if (is_prime(query)) {
    std::cout << "prime" << std::endl;
  } else {
    std::cout << "composite" << std::endl;
  }
}

[Duthomhas]

It is really hard to answer really simple questions like this without actually giving away the answer.

The assignment gives you very specific suggestions about how to avoid testing all numbers less than x. It also gives you a very specific suggestion on how to halve the number of numbers you test beyond that.

Try writing the function as simply as possible (test all numbers from 2 to N-1), then think about each of the suggestions and see how to reduce the number of tests you must perform.

Good luck!