How to check if a number is prime or not ?

[mystic phoenix]

hey ! I am super new to coding and trying to learn c as my first language (not wanna discuss about the best language for beginners), I stumbled upon a website and tried solving some easy series kind of questions, but couldn't actually understand most of it. I tried writing it on my own as far as I can, but it almost works for all numbers except 2, because of int i = 2. So, my question is, is there any easier and also time efficient way to check if a number is prime, cause I am not aware of most of the advanced stuff like recursion.
Also, sorry if this isn't an appropiate level question to ask here ~

[plain plume]

When your question is answered use !solved to mark the question as resolved.

Remember to ask specific questions, provide necessary details, and reduce your question to its simplest form. For tips on how to ask a good question use !howto ask.

@mystic phoenix

Screenshots!

Your message appears to contain screenshots but no code. Please send code and error messages in text instead of screenshots if applicable!

[mystic phoenix]

Code: ```#include <stdio.h>

int main() {
int n;
printf("Enter a number: ");
scanf("%d", &n);

for (int i = 2; i < n; i++) {
if (n % i != 0) {
printf("%d is a prime number\n", n);
} else {
printf("%d is not a prime number\n", n);
}
break;
}

return 0;

}```

Error: Not able to check the condition for value of n = 2

[dull pilot]

This approach may be what you are looking for:

#include <stdio.h>

int main() {

    int n, tmp = 0;

    // Get user input.
    printf("Enter a number: ");
    scanf("%d", &n);

    // Iterate up to n/2.
    for (int i = 2; i <= n / 2; i++) {
        // Check if n is divisible by any number.
        if (n % i == 0) {
            tmp++;
            break;
        }
    }

    // Check for the value of tmp and n.
    if (tmp == 0 && n != 1) {
        printf("%d is a prime number\n", n);
    }
    else {
        printf("%d is not a prime number\n", n);
    }

    return 0;
}

Let me explain the code a little bit

[dull pilot]

Here we use a temporary variable to check if our number is prime, and this tmp variable is set to 0 at the start of the program.

The for loop iterates from i = 2 to i <= n /2, in each iteration we're check if nis perfectly divisible by i.

If it is, aka there is no reminder, them tmp will be set to 1 and the loop will stopped, else the loop will end after i is greater than n/2, and tmp's value won't change.

Depending on the loop result, we check tmp 's value and we ensure that n is not 1, for good measure, because someone may actually input 1.

If both cases, tmp being 0 and and n being not 1 are satisfied, then effectively, the inputted number is prime.

[cyan gate]

It is enough to check only odd numbers up to sqrt(n). I.e. for(...; i * i <= n; i += 2)

Also a good idea to check scanf return value

if(scanf(" %d", &n) != 1){
  printf("Invalid input\n");
  return 1;
}

Or something like this

[dull pilot]

Wait, scanf return int too? Huh, didn't know that, I should check the manual.

[soft mist]

You could put this in a function that returns a boolean (bool isPrime(int n)) and then handle small numbers up front before your loop:

if (n <= 1) return false;
if (n <= 3) return true; // 2 and 3 are prime
if (n % 2 == 0 || n % 3 == 0) return false; // No multiples of 2 or 3

Then your loop can start at 5 and skip multiples of 2 or 3 up to square root of n since you have already checked these for a little more efficiency.

for (int i = 5; i * i <= n; i += 6) {
    if (n % i == 0 || n % (i + 2) == 0) {
        return false;
    }
}
return true;

[mystic phoenix]

hey thanks for sharing this, I will definitely try it out !

[mystic phoenix]

tyy!!! although functions are not yet taught in our class, so I have a little difficulty understanding the working of them, but I will try implementing it for sure. Thanks for answering my question.

[mystic phoenix]

hey hugging! thanks for sharing this, from what I understand is it will return 1 as a false value for the condition, when we try to input some value that is not an integer ? please correct me if I am wrong.

[cyan gate]

scanf returns the number of things that it has successfully read. Here we want to read 1 number, so we want it to return 1. If it returns something else, this means the function failed to read the input. (For example, if user inputs a string instead of an integer)

There are various ways to handle a failure. You could for example, keep retrying to ask the user for input until the scanf operation is successful.

I chose to just terminate the program with an error code. (return 1;)

[plain plume]

@mystic phoenix Has your question been resolved? If so, type !solved :)

[mystic phoenix]

the scanf returns the number of things it has successfully read.
so will it read strings too ?

Here we want to read 1 number, so we want it to return 1. If it returns something else, this means the function failed to read the input.
so do we use another type of return if we wanna read lets say strings or characters ?

[cyan gate]

It will read characters with %c

It can read strings, but it's kind of a bad idea. For strings, I prefer to use another function

[mystic phoenix]

btw why do we used return 1, when we already printf("Invalid input\n"); after the condition ?

[cyan gate]

Because if we don't return, then the code will continue to execute as if everything is ok, when in reality it is not ok, and in the variable n we have some unknown garbage value

[mystic phoenix]

ooo, but can't we just use break; instead of return 1 in that case ?

[cyan gate]

Break can only be used in while, for loops and in switch statements

[mystic phoenix]

ahh I see !

I think I got it, ty

[mystic phoenix]

hey nulldott! thanks for the code, not sure if it is much to ask but I tried understanding the use of that extra tmp variable you used in your code, but failed to understand why you actually added it ?

[cyan gate]

This is basically a "flag" variable

[mystic phoenix]

a flag variable

[cyan gate]

If it's 0, then number is prime. If 1, then not prime. Initially it is set to 0. i.e. kind of, every number is assumed to be prime, until proven otherwise 🤣

[mystic phoenix]

ohh

[cyan gate]

If it turns out that the number has a divisor, then it gets set to 1

[mystic phoenix]

thanks I understand it now

!solved

[plain plume]

Thank you and let us know if you have any more questions!

This thread is now set to auto-hide after an hour of inactivity

[dull pilot]

Thanks for responding to them, I was about to but I got busy.

You're the best

[nova crescent]

@mystic phoenix Even though you already closed the thread, maybe a little extra to add onto this:
The most efficient ways to verify if a number is prime or not are actually probabilistic ones, i.e. functions that return true if a number is probably prime and false if the number is definitely not prime (i.e. it allows for false negatives but not for false positives).

Here's some Java source code that shows such a function:

/**
 * Returns {@code true} if this BigInteger is probably prime,
 * {@code false} if it's definitely composite.
 *
 * This method assumes bitLength > 2.
 *
 * @param  certainty a measure of the uncertainty that the caller is
 *         willing to tolerate: if the call returns {@code true}
 *         the probability that this BigInteger is prime exceeds
 *         <code>(1 - 1/2<sup>certainty</sup>)</code>. The execution time of
 *         this method is proportional to the value of this parameter.
 * @return {@code true} if this BigInteger is probably prime,
 *         {@code false} if it's definitely composite.
 */
boolean primeToCertainty(int certainty, Random random) {
    int rounds = 0;
    int n = (Math.min(certainty, Integer.MAX_VALUE-1)+1)/2;

    // The relationship between the certainty and the number of rounds
    // we perform is given in the draft standard ANSI X9.80, "PRIME
    // NUMBER GENERATION, PRIMALITY TESTING, AND PRIMALITY CERTIFICATES".
    int sizeInBits = this.bitLength();
    if (sizeInBits < 100) {
        rounds = 50;
        rounds = n < rounds ? n : rounds;
        return passesMillerRabin(rounds, random);
    }

    if (sizeInBits < 256) {
        rounds = 27;
    } else if (sizeInBits < 512) {
        rounds = 15;
    } else if (sizeInBits < 768) {
        rounds = 8;
    } else if (sizeInBits < 1024) {
        rounds = 4;
    } else {
        rounds = 2;
    }
    rounds = n < rounds ? n : rounds;

    return passesMillerRabin(rounds, random) && passesLucasLehmer();
}

Source: https://github.com/openjdk/jdk/blob/master/src/java.base/share/classes/java/math/BigInteger.java#L1001

Basically what this code does is it uses the Miller-Rabin primality test aswell as the Lucas-Lehmer primality test

A simpler concept for something probabilistic would be a probabilistic data structure called a Bloom filter (maybe you've heard of them already).
Bloom filters are used to test whether an element is a member of a set. False positives are possible, but false negatives are not (i.e. it tells you either that something is possibly in the set or that it's definetly not in the set). Bloom filters are incredibly space efficient and can often speed up processes.

[mystic phoenix]

hey monke ! thanks for taking out your time explaining the most efficient way to check if a number is prime or not, although I am not that proficient in programming yet, I still appreciate your way of explaining things. And will ofc save it up for future reference as I get better in problem solving!