-1

I am new to C++ and coding, so excuse me if my knowledge is poor. I thought of a way to check if a number is prime (my code is below). My idea is that the user inputs a number, and uses a for loop with a variable i increasing in +1 increments until it equals to the inputted number. Each time this increment happens, i is tested for being a factor of the inputted number. If it's a factor, the result of the modulus operator will be zero. In this case a variable remainders is incremented by +1, and, after all the values for i have been tested, if the value of remainders is 2, the tested number is prime, otherwise it is not prime. My code is below, please inform me whether my idea is correct.

#include <iostream>
using namespace std;

int main () {
int userNumber;
int remainders = 0;
cout << "Input the number to be tested:";
cin >> userNumber;

for (int i = 0; i == userNumber; i++){
        int remainderTest = userNumber % i;
    if (remainderTest = 0) {
        remainders ++;
    }
}

if (remainders == 2) {
    cout << "The number you inputted is prime!";
} else {
cout << "The number you entered is not prime!";
}

return 0;
}
zkoza
  • 2,644
  • 3
  • 16
  • 24
DawsUTV
  • 35
  • 1
  • 2
  • 3
    `if (remainderTest = 0)` assigns 0 to `remainderTest` and then evaluates the condition, so it is always false. Besides the point really though since the loop `for (int i = 0; i == userNumber; i++)` will never be entered unless the user enters 0. – Retired Ninja Jan 04 '22 at 23:58
  • 2
    Easiest way to check if code works is to write some test cases and run the code. – Fantastic Mr Fox Jan 05 '22 at 00:04
  • 3
    You cannot take a modulo of 0. Just start at 3, and increment by 2 every time. 2 is an exception. – paddy Jan 05 '22 at 00:05
  • 1
    Two problems with the for loop. Starting at 0 ensures a divide by 0 error, and the loop condition is only true if `i` and `userNumber` are the same, once again only possible with 0. Perhaps you meant `i < userNumber`? – Retired Ninja Jan 05 '22 at 00:10
  • 2
    Lot of algorithm to find prime numbers are **well known**... It should be easy to find one. Having said that, it is pointless to test even number (except 2) and no need to test above square root of a number. So if you want to test `623`, you should test `2, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21 and 23` **at most**. In that case, you will find that it is not prime because `632 / 7 = 89`... – Phil1970 Jan 05 '22 at 00:44
  • see https://stackoverflow.com/a/22477240/2521214 – Spektre Jan 06 '22 at 09:00

3 Answers3

2

OP's code fails in various ways.

  • for (int i = 0; i == userNumber; i++){ only iterates the loop when userNumber == 0 - and then only once.

  • Code attempts userNumber % 0 which is undefined behavior (UB).

  • Code assigns rather than compares with if (remainderTest = 0)

Even if the loop iteration was fixed, OP's code is slow: O(n).

A short prime test algorithm to help OP along.

It iterates until i exceeds n/i. (Tip: avoid i*i <= n)

bool prime_test(int n) {
  for (int i = 2; i <= n/i; i++) {
    if (n%i == 0) return false;
  }
  return n > 1; 
}

The one above is very short, yet still fast: O(sqrt(n)) and works for all int n: [INT_MIN...INT_MAX].

Of course there are many potential optimizations, albeit with more code.

A favorite first optimization is to handle even numbers.

bool prime_testA(int n) {
  if (n % 2 == 0) {  // If even ...
    return n == 2;
  }
  for (int i = 3; i <= n/i; i += 2) { // Go up by 2
    if (n%i == 0) return false;
  }
  return n > 1; 
}
chux - Reinstate Monica
  • 143,097
  • 13
  • 135
  • 256
  • You can change the condition from `i <= n/i` to `i * i <= n` to save a division. Although the optimizer could combine it with the n%i calculation. – Sebastian Jan 05 '22 at 08:32
  • 1
    @Sebastian "change the condition from i <= n/i to i * i <= n to save a division" --> A reasonable good compiler sees the nearby `n/i` and `n%i` and emits efficient code, doing both for the price of one - if not, see `div()`. Yet the suggestion to use `i * i <= n` leads to _undefined behavior_, possible an infinite loop, when `n` is a prime near `INT_MAX`. With 32-bit `int`: `INT_MAX` is 2,147,483,647, a _prime_. Obviously `i*i <= INT_MAX` is never false unless with UB. Best to stick with `i <= n/i` to "works for all `int n`" than save a division and have code that fails corner cases. – chux - Reinstate Monica Jan 05 '22 at 13:52
  • Ok, you are right, this would need another test at the beginning for large n. Thank you for the advice. `avoid i*i <= n` is a bit strong IHMO to say generally. ;-) – Sebastian Jan 05 '22 at 14:09
  • @Sebastian Avoiding overflow is a good thing. Learn how in small things to avoid such problems in [large things](https://en.wikipedia.org/wiki/Ariane_flight_V88#Launch_failure). – chux - Reinstate Monica Jan 05 '22 at 14:21
  • `i <= n/i` -> `i <= sqrt(n/i)` – Oleg Cherednik Jan 05 '22 at 22:37
  • @oleg.cherednik Perhaps you meant not `i <= sqrt(n/i)`, but `i <= sqrt(n)`? IAC, `sqrt(n)` has various corner cases that lead to trouble. `sqrt(some negative)` is a domain error. `sqrt(some integer type)` casts to `double`. On select machine, `int` is wider than 54 bits, or code is really using `long long`, etc., the conversion of an integer to `double` before the call may round down and form a square root slight smaller than needed limit. Weak compilers may not see constancy of the `sqrt(n)` & so call the somewhat expensive function repeatedly. Best to use integer math for an integer problem. – chux - Reinstate Monica Jan 05 '22 at 22:56
  • @oleg.cherednik What would make some sense is to call `if (n < 0) return false; int limit = isqrt(n); for (int i = 2; i <= limit; i++) { ...`. That idea is really already covered under "there are many potential optimizations with more code.". Above is just some _simply_, yet reliable code for all `int`. – chux - Reinstate Monica Jan 05 '22 at 23:00
  • @chux-ReinstateMonica yes, I mean ‘i <= sqrt(n)’. Sorry for typo. – Oleg Cherednik Jan 06 '22 at 07:23
1

Firstly, i think that you should declare i=2, because it is useless to modulo 0 or 1. Secondly, why you declare i=0, and after that i==userNumber :)) Beside, in line 12, it ==, not =. Your code (after fixed):

#include <iostream>
using namespace std;

int main () {
int userNumber;
int remainders = 0;
cout << "Input the number to be tested:";
cin >> userNumber;

for (int i = 2; i <= userNumber; i++){
        int remainderTest = userNumber % i;
    if (remainderTest == 0) {
        remainders ++;
    }
}

if (remainders == 1) {
    cout << "The number you inputted is prime!";
} else {
cout << "The number you entered is not prime!";
}

return 0;
}
-1

Your code has an in the for loop. Instead of i == userNumber, it should be i < userNumber. Here's an implementation of your idea as a function:

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

You don't need to account for 1 and n being factors of any n if you don't include them in the for loop condition by starting at 2 and ending at n, so there is no need to keep track of remainders through a variable.

Aprameya Tirupati
  • 9
  • 2