CODEWITHSUNDEEP
c++cnumbers
user3359196
user3359196

Reputation: 15

C programming - finding prime numbers

A friend gave me this code to find the prime numbers from 1-40

#include <stdio.h>
#include <conio.h>

void main(void)
{
    clrscr();

//print prime numbers from 1-40

int i, j;
int factor = 0; //this will be 1 if a factor is found
        //otherwise 0
        //so factor = 1 means not a prime number

printf("Prime numbers from 1 to 40 are: ");
for (i = 1; i < 41; i++)
{
    for (j = 2; j <= (i / 2); j++)
    {
        if (factor == 0)
        {
            if (i % j == 0)
                factor = 1;
            else
                factor = 0;
        }
    }
    if (factor != 1)
    {
        printf("%d ", i);
    }
    factor = 0;
}
getch();

}

I don't get the 2nd part of the loop.. why does j start with 2, and why is it less than (i / 2) and not i?

Thanks.

Upvotes: 1

Views: 2519

Answers (4)

VINOTH ENERGETIC
VINOTH ENERGETIC

Reputation: 1843

why does j start with 2

What is prime number?
A prime number (or a prime) is a natural number greater than 1 that has no positive divisors other than 1 and itself.

note the keyword other than one. 

and why is it less than (i / 2) and not i?

There is a rule for prime number “If the number cannot be divisible by below the sqrt double that number then it is an prime number”. So check up to the sqrt of double that number.

Check here for more optimization

PRIME NUMBER PROGRAM FOR LARGE NUMBERS WITH 6 EFFICIENCY METHOD HANDLED

Upvotes: 1

Mike Seymour
Mike Seymour

Reputation: 254431

why does j start with 2

Because 1 is a factor of all numbers (including primes), so you don't test for that. (The outer loop should probably start from 2 as well since, by convention, 1 usually isn't regarded as prime.)

and why is it less than (i / 2) and not i?

There's no need to check for factors larger than the square-root of i since, if there is such a factor f, there will also be a factor i/f which is smaller than the square root.

But square roots are hard to calculate, so this version uses i/2 as a simpler but looser upper bound. It's at least as large as the square root, as long as i is at least 4.

Upvotes: 3

Thayne
Thayne

Reputation: 6992

It starts with 2, because 2 is the smallest prime number (1 isn't considered prime) and ends at i/2 because the largest factor of a number n is at most n/2.

If it started at 1 you wouldn't find any prime numbers, because every number is divisible by 1.

As for the second part, I will use a proof by contradiction. Suppose n is divisible by a number m greater than n/2. Then n is also divisible by n/m but m>n/2 implies2*m > nwhich means that n must be divisible by an integer less than 2, but the only such integer is 1, which would imply thatm=1`. Therefore n can have no divisors between n/2 and n.

Upvotes: 1

user376507
user376507

Reputation: 2066

You need to start finding if the given number is divisible by 2, 3, ... till half the value of the number you are looking for. A number is not prime if it is divisible by any number lesser than it without leaving a remainder. Once you reach half the value of the number you need to check for the rest of the numbers.

Upvotes: 0

Related Questions