How can you print prime numbers uing turbo c?

Answer 1

A Prime number is a number that has no factors other than 1 and itself. For instance, 1, 2 and 3 are prime numbers. However, 4 isn't because it can also be divided evenly by 2.

Although a complicated floating-point function can be written to test if the division of a number is even, the C modulus operator (%) is far quicker. If 'n' modulus 'm' is zero, then the division is even - there is no fractional component.

Using this rule, the pseudo-code for testing if a number is prime is as follows:

- if number is zero, return false

- if number is less than 4, return true since 1, 2 and 3 are primes

- iterate a variable 'c' from 2 until the number 'n' minus 1

- if n modulus c is zero, return false, since 'n' has 'c' as a factor

- return true

All that remains is converting the above code to C (or any other programming language) using inline code or a function.

Answer 2

A prime number is a number that is greater than 1 that has no prime factors other than 1 and itself. For instance, 2 and 3 are prime numbers but 4 is not because it can be divided by 2 (which is neither 1 nor itself). Thus 4 is a composite number, as are all even numbers except 2.

0 is not prime because it has infinite factors (any value greater than 0 will divide into 0 with no remainder). 1 is also not prime because it has only one factor; itself. All prime numbers must have two, and only two, different factors (1 and itself). 2 is the only even prime and is also the first prime.
For all odd values greater than 2, we must divide the value by all potential factors greater than 2 but less than the value. If the value can be evenly divided by any of these potential factors then the value cannot be prime and we can stop testing. Note that there can be no even factors in an odd value because if 2 is not a factor then neither is 4, 6, 8, and so on. Therefore we start with potential factor 3 and then try 5, 7, 9, 11 and so on. In other words, we only test the potential odd factors.

The maximum potential factor is the square root of the value. This is because if any factor greater than the square root exists, then there has to be a corresponding factor that is less than the square root. It therefore follows that if there is no factor below the square root then there cannot be one larger than the square root. For example, if the value were 29 then we'd naively test the factors 3, 5, 7, 9, 11 and 13. But once we've ruled out 3 and 5 we can stop because if 7 really were a factor, then either 3 or 5 must also be a factor which is clearly not the case. The square root of 29 is approximately 5.385, so we can stop once we've tested 5.

Based upon this we can now naively determine if a number is prime or composite by the following algorithm:

- if the number is less than 2 then it is composite.

- if the number is even, then it is prime if and only if it is 2, otherwise it is composite.

- if the number is odd then it is prime if and only if it has no odd factors from 3 to its square root (inclusive), otherwise it is composite.

The reason this is naive is because we are dividing by all odd factors when we only really need to divide by all odd prime factors. A prime factor is a factor that is also prime. 9 is not a prime factor because it is a multiple of 3, so any value not divisible by 3 cannot be divisible by 9, 27, 45, 63 and so on, so we can eliminate these multiples of 3 as factors. By the same token, any number not divisible by 5 cannot be divisible by 15, 25, 35 and so on, so we can eliminate these as well. If we eliminate all the non-prime factors we greatly reduce the time it takes to determine if a number is prime or not, particularly when that number is extremely large.

If we consider the value 4,294,967,291, the square root is approximately 65,536. If we were to test every odd factor then we'd need to perform up to 32,768 divisions. However, if we exclude non-prime factors we'd only have to perform 6,542 divisions because that's how many prime factors there are in the range 3 to 65,536. In other words, we could determine that 4,294,967,291 was prime in just 1/5th of the time it would take to check every odd factor.

The way we achieve this is to create a lookup table that contains all the prime factors. This means we must generate those primes, which means we must also test them to see if they are prime. But this is easily achieved because we can use the lookup table itself to test each potential prime factor. We already know that 3 is a prime factor, so we can make that as our first prime factor (we don't need 2 because that is automatically catered for by our algorithm above).

Calculating all 6,542 prime factors takes but a fraction of a second on a reasonably fast machine. If we store that table as a static array that is generated the first time we test for a prime, we can test all potential primes quite efficiently.

Thus our algorithm now becomes:

- generate prime factors (one-time-only).

- if the number is less than 2 then it is composite.

- if the number is even, then it is prime if and only if it is 2, otherwise it is composite.

- if the number is odd then it is prime if and only if it has no prime factors up to its square root (inclusive), otherwise it is composite.

The following example program is written in C++, but uses C-style code that can be easily converted to classic C.

#ifdef __cplusplus

extern "C" {

#endif

#include

#include

#include

int is_prime (const unsigned num)

{

static const unsigned prime_factor_count=6542;

static unsigned prime_factor[prime_factor_count];

static int been_here=0;

unsigned index;

if (!been_here)

{

/* one-time-only initialisation */

const unsigned max_factor=(unsigned)sqrt((float)0xffffffff)+1;

unsigned count, factor;

count=1;

factor=3;

prime_factor[0]=factor;

while ((factor+=2)<=max_factor)

{

for (index=0; index

{

if (!(factor%prime_factor[index]))

{

break;

}

}

if (index==count)

{

prime_factor[count++]=factor;

}

}

been_here = -1;

assert (count==prime_factor_count);

}

/* 2 is the first prime */

if (num<2)

{

return 0;

}

/* 2 is the only even prime */

if (!(num&0x1))

{

return num==2;

}

/* num is odd, so test all prime factors */

const unsigned max=(unsigned) sqrt ((float) num) + 1;

for (index=0; index

{

if (!(num%prime_factor[index]))

{

return 0; /* not prime */

}

}

return -1; /* prime */

}

void test (const unsigned num)

{

if (is_prime (num))

printf ("%u is prime\n", num);

}

int main()

{

/* test the largest 4-byte prime (4,294,967,291) */

test (0xfffffffb);

/* test all values up to 16,777,215 (may take a few minutes) */

for (unsigned num=0; num<0xffffff; ++num)

test (num);

}

#ifdef __cplusplus

}

#endif