Prime Numbers & Arrays

**SCRIPT_KITTEH** · 05-27-2013

Hi folks,

I was going through a book I have about C trying to learn about arrays, and one of the first few examples of what could been done with an array was showing how to use an array to generate a list of prime numbers. I've been staring at this program for about an hour trying to understand how it works (it does), but the workings of one for loop within the program absolutely confuses me. I was hoping y'all could help me understand. This is the program: ( I commented out the for loop that I don't understand ).

Code:

#include <stdio.h>
#include <stdbool.h>

int main () {

        int     p, i, primes[50], primeIndex = 2;
        bool    isPrime;

        primes[0] = 2;
        primes[1] = 3;

        for ( p = 5; p <= 50; p += 2 ) {
                isPrime = true;

          /*      for ( i = 1; isPrime && p / primes[i] >= primes[i]; i++ )
                        if ( p % primes[i] == 0 )
                        isPrime = false;   */

                if ( isPrime == true ) {
                        primes[primeIndex] = p;
                        primeIndex++;
                }
        }

        for ( i = 0; i < primeIndex; i++ )
                printf ( "%i ", primes[i] );

        printf ( "\n" );
        return 0;

}

The loop condition in particular is the part that I don't understand...

Code:

isPrime && p / primes[i] >= primes[i]

So that is saying in order for this loop to go on, really two conditions must be met since there's that && operator. isPrime must be true (I think that's what it means by just having "isPrime" and not setting it equal to anything) and p / primes[i] must be greater than or equal to primes[i].

So at the beginning of the loop, since i = 1, p = 5 (as per surrounding loop), and prime[i] = 3 ( as per the variable assignment at the beginning of the program ), the loop condition would be "isPrime && 5 / 3 >= 3"

"5 / 3 >= 3" WTF??? The loop should stop right there! 1.666666667 is NOT greater than or equal to 3!

What am I missing here? Obviously I'm misinterpreting or not seeing something, but I can't figure out what that is...

Any ideas?

**ZuK** · 05-27-2013

"5 / 3 >= 3" WTF??? The loop should stop right there! 1.666666667 is NOT greater than or equal to 3!

this is integer division 5 / 3 equals 1
Kurt

**SCRIPT_KITTEH** · 05-27-2013

Originally Posted by ZuK

this is integer division 5 / 3 equals 1
Kurt

Oh yeah... This is true but it still confuses me as to how this loop gets past even that when 1 is not greater than or equal to 3.

**ZuK** · 05-27-2013

The loop needn't go on. 5 was found to be the next prime number. The program continues with the outer loop with p as 7. see what happens then
Kurt

**stahta01** · 05-27-2013

Do the logic using 9; it is NOT supposed to continue on for 5 and 7 because they are prime.

Tim S.

**rcgldr** · 05-27-2013

One reason the loop breaks if isPrime is set to false which only happens if a test number p module a number in the array primes == 0, meaning the test number p is exactly divisible by one of the previous found prime numbers, meaning that the test number p is not prime. The other reason the loop breaks is if the test number p / prime[i] >= prime[i], which is essentially stopping when a prime number squared (prime[i]*prime[i]) is greater than the test number p. The comparison is p / prime[i] >= prime[i], since the integer division rounds down. For example, 11/2 = 5 >= 2, so the loop continues, 11/3 = 3 >= 3, so the loop continues, 11/5 = 2 and is not >= 5, so the loop stops since 5^2 is greater than 11, and it adds 11 to the list of prime numbers.

**Nominal Animal** · 05-27-2013

Perhaps this pseudocode version helps make it easier to understand?

Code:

primes = { 2, 3 }

for p in 4..50, odd numbers only:

    start by assuming p is prime:
    isPrime = true
    
    for t in primes:
        if t*t > p then:
            break
        if p is divisible by t, then:
            isPrime = false
            break

    if isPrime == true, then:
        add p to primes

There are only two kinds of natural numbers (positive integers) smaller than p: primes, and compound numbers. Compound numbers smaller than p are products of two or more primes equal to or smaller than square root of p.

Thus, it is enough to test whether p is divisible by any prime <= sqrt(p). If it is divisible, then p is not a prime; otherwise, p is a prime.

Oh, and like rcgldr said above, testing (p / n >= n) is the same as testing (p >= n*n) when both p and n are positive integers, except the former will work (not overflow) for all positive integers the integer type can represent. The latter will overflow when n is greater than the square root of the largest representable integer value.

**SCRIPT_KITTEH** · 05-27-2013

Originally Posted by ZuK

The loop needn't go on. 5 was found to be the next prime number. The program continues with the outer loop with p as 7. see what happens then
Kurt

Originally Posted by stahta01

Do the logic using 9; it is NOT supposed to continue on for 5 and 7 because they are prime.

Tim S.

Reading these responses made me realize where I was derping. I wasn't viewing this inner loop as simply a Program Statement of the outerloop, which means that whether or not the Program Statement of the inner loop ever gets around to happening has no bearing on whether or not the outer loop continues.

Originally Posted by rcgldr

One reason the loop breaks if isPrime is set to false which only happens if a test number p module a number in the array primes == 0, meaning the test number p is exactly divisible by one of the previous found prime numbers, meaning that the test number p is not prime.

Yup, this makes sense.

Originally Posted by rcgldr

The other reason the loop breaks is if the test number p / prime[i] >= prime[i],

I understand now how this condition not being satisified doesn't bring the whole program to a halt, but I'm going to have to let the fact that this is the same as (prime[i])^2 >= p roll around in my head for a while. I don't see it yet, but I'm going to re-read yours and Nominal Animal's responses until I understand... I'm pretty bad at math.

Originally Posted by Nominal Animal

Perhaps this pseudocode version helps make it easier to understand?

Yes, actually. Believe it or not before I saw your reply I had done something similar, I don't know if it is also "psuedocode" but I tried to write down how the program flows just using words, and it helped.

Originally Posted by Nominal Animal

There are only two kinds of natural numbers (positive integers) smaller than p: primes, and compound numbers. Compound numbers smaller than p are products of two or more primes equal to or smaller than square root of p.

Interesting, I had never heard of compound numbers. I understand why this inner loop doesn't stop the whole program if it's not satisfied now, but I'm not comprehending yours and rcgldr's mathematical explanations of why p / primes[i] >= primes[i] works here, but I'm going to keep reading until I get it.

Thank you all for your responses, as always. There's no way I would have even gotten close to the small understanding of C that I do have if it wasn't for you guys. *e-hug*

**SCRIPT_KITTEH** · 05-27-2013

wait a sec... ( p / n >= n ) == ( p > = n * n ) because to move that n to the other side of the operator you have to multiply to cancel out the n being divided O_O

yaaay

**Nominal Animal** · 05-27-2013

Originally Posted by SCRIPT_KITTEH

Interesting, I had never heard of compound numbers.

No wonder, because I meant composite numbers instead of compound numbers. Sorry for the confusion.

(And you're spot on why (p / n >= n) is the same as (p >= n*n) for positive integers. The former is used because the latter may overflow.)

I'm not comprehending yours and rcgldr's mathematical explanations of why p / primes[i] >= primes[i] works here, but I'm going to keep reading until I get it.

The trick here is that the loop is not testing whether some random positive integer p is prime or not.

The loop tests whether p is prime, when all primes smaller than p are known and listed in primes.

All positive integers are either primes, or products of primes (== composite numbers). So, if p is not divisible by any prime smaller than p, it is prime.

The square root comes from the nature of the composite numbers. If you have a composite number p,

p = p₁ × ... × p_N

there is always at least one factor equal to or smaller than the square root of p. Remember: p₁, p₂, ..., p_N are all primes by definition!

Proof: Let K is the smallest integer larger than sqrt(p), where p is a natural number.
We can immediately tell that K² > p
In fact, K^N > p for all N >= 2, and therefore, a composite p must contain at least one factor equal to or smaller than the square root of p.

This means checking all primes <= sqrt(p) is enough.
A composite positive integer p has at least one prime factor that is equal to or less than the square root of p.

**rcgldr** · 05-27-2013

Originally Posted by Nominal Animal

And you're spot on why (p / n >= n) is the same as (p >= n*n) for positive integers.

Note the previous posts that mentioned "p greater than n*n" should have stated "p greater than or equal to n*n". (too late to edit those now).

**rcgldr** · 05-27-2013

Since multiplication is much faster than division, it's probably better to add a separate check for prime[i] greater than sqrt(2^31). Example program:

Code:

/* assuming 32 bit environment */

#include <malloc.h>
#include <stdio.h>

/* will allocate 1GB of ram */
#define ARRAYSIZE 0x10000000

/* SQRTMAX = ceil sqrt((2^31)) */
#define SQRTMAX 46341u

/* max PRIMEMAX for this example program is 7FFFFFFFu */
#define PRIMEMAX 0x7FFFFFu

int *primes;

int main ()
{
unsigned int p, i, primeIndex = 2;
unsigned int isPrime;

    primes = malloc(ARRAYSIZE * sizeof(int));

    primes[0] = 2;
    primes[1] = 3;

    for(p = 5; p <= PRIMEMAX; p += 2){
        isPrime = 1;
        for(i = 1; isPrime && primes[i] < SQRTMAX && p >= (primes[i] * primes[i]); i++)
            if(p % primes[i] == 0)
                isPrime = 0;
            if(isPrime == 1){
                primes[primeIndex] = p;
                primeIndex++;
            }
        }

    printf("prime[%10d] = %10d\n", primeIndex-1, primes[primeIndex-1]);

    free(primes);

    return 0;
}

**SCRIPT_KITTEH** · 05-28-2013

Originally Posted by Nominal Animal

There are only two kinds of natural numbers (positive integers) smaller than p: primes, and compound numbers. Compound numbers smaller than p are products of two or more primes equal to or smaller than square root of p.

Thus, it is enough to test whether p is divisible by any prime <= sqrt(p). If it is divisible, then p is not a prime; otherwise, p is a prime.

Just wanted to say that after sleeping on it and coming back and looking at all of this again this evening, I finally see all of this with clarity

for example:

when p = 9,

prime factors of composite #'s smaller than p:

8 == 2 * 2 * 2 *2
6 == 2 * 3
4 == 2 * 2

all of which are <= to the square root of nine, which makes them suitable to be divided into 9 to test whether or not 9 is a composite number, which this test reveals as yes

Thank you guys for helping me see this!

**rcgldr** · 05-28-2013

I made an unsigned version that works in 32 bit mode, up to 2^32-1. The largest prime number in this range is 2^32 - 5 = 4294967291. On my system, Intel i7 2600K 3.4ghz, DP67BG motherboard, 4GB ram, Windows XP, this example program takes about 71 minutes to run.

The compiler is dividing in order to do the modulo (%), so to speed up the program a bit, I changed the code to save the quotient (q = p / prime[i]) >= prime[i], and then used (q * prime[i]) == p to check for a non prime. I also removed isPrime and replaced the logic to break out of a nested loop with a goto.

Code:

/* assuming 32 bit environment */

#include <malloc.h>
#include <stdio.h>
#include <time.h>

/* allocate 1 GB */
#define ARRAYSIZE 0x10000000u

/* largest prime < 0x10000 == 0xFFF1 */
#define SQRTMAX 0xFFFFu

/* 2^32 - 1 */
#define PRIMEMAX 0xFFFFFFFFu

clock_t dwTimeStart;    /* clock values */
clock_t dwTimeStop;

unsigned int *primes;

int main ()
{
unsigned int p, q;
int i;
int px = 2;

    primes = malloc(ARRAYSIZE * sizeof(unsigned int));
    if(primes == NULL)
        return(0);

    dwTimeStart = clock();

    primes[0] = 2u;
    primes[1] = 3u;

    for(p = 3; p < PRIMEMAX;){
        p += 2;
        for(i = 1; ; i++){
            if((q = p / primes[i]) < primes[i])
                break;
            if((q * primes[i]) == p)
                goto loop0;
        }
        primes[px] = p;
        px++;
        if(px >= ARRAYSIZE)
            break;
        if((px & 0xfffffu) == 0)
            printf("prime[%10u] = %10u\n", px-1, primes[px-1]);
loop0:
    continue;
    }

    dwTimeStop = clock();

    printf("prime[%10u] = %10u\n", px-1, primes[px-1]);

    printf("number of ticks   = %10u\n", dwTimeStop - dwTimeStart);

    free(primes);

    return 0;
}

**SCRIPT_KITTEH** · 05-28-2013

Originally Posted by rcgldr

(q = p / prime[i]) >= prime[i], and then used (q * prime[i]) == p

Nice. Why is multiplication faster though?

I tried to compile your program but I got some error messages, I am running 64 bit Linux tho. I wish it worked because I wanna put this baby's speed to the test

4x Intel(R) Core(TM) i5-3317U CPU @ 1.70GHz
16gb ram
64gb SSD for OS and 512 gb SSD for other stuff

Thread: Prime Numbers & Arrays

Thread Tools

Search Thread

Display

Prime Numbers & Arrays

Similar Threads

Need help for find prime numbers among from 50 numbers... please anyone help me...

the longest increasing subsequence of prime numbers whose reverse numbers are prime

non prime numbers or composite numbers program.help plz!

prime numbers

Finding and Printing prime numbers using arrays