Thread: Prime Numbers, Modulus Operator Help

Originally Posted by dcwang3

see that's what the graduate student did not teach us, about using sqrts and stuff, so could you enlighten me about that, thanks. Where does the square root come into play? I suppose it's the method of finding a prime number? For a remainder, how do you know if it should be i%j or visa versa

Lets say we have a composite number C with sqrt(C) = R. For any factor F1 of C there exists a cofactor F2 = C/F1. Either F2 > F1, F2 < F1, or F2 == F1. If F1 == F2 == R then F1 is the sqaure root of C (F1 * F2 == F1 * F1 == C). F1 < F2 then F1 must be less than R since F2 must be greater than R in order for F1 * F2 to equal R * R == C. Since one fo F1 or F2 is less than R you only need to search values less than or equal to R to find a factor of C.

If C has no factor less than or equal to R then it cannot have a factor greater than R.

Furthermore, you need only check PRIME factors less than or equal to R, since any composite factor will itself have a factor less than itself which will either be prime, or ultimately reduceable to a prime.

And further, all prime number can be written as the sum of a prime number and the primorial of some prime less than itself. P1 + P2! where P2! indicates the primorial of P2 (they dont have the primorial symbol in the character set) and P1 > P2.

Even further, you need only check P2! + P1 for values of P1 > P2 and less than P3! where P3 is the prime number that immediately follows P2.

Originally Posted by Adak

"Somehow linking" later on, in a simple program, is not the approach you want to take. As much as anything else, the problems are to get you thinking about how you could provide answers, as you calculate them.

You COULD write the primes out to a file, and then go back and count off the first N number of primes for your answer - but that's way inefficient. You already have the answers when you first calculate them, so just count them and print them to your screen.

Vart's pseudo code is what you should be looking at. I attempted to modify your code using for loops, but it's just not as elegant:



This is the sort of thing I believe you wanted.

This is completely untested code, so don't be surprised if it's not working.

Using names that have meaning, for your variables, will make de-bugging your code so much easier, both at the time you write it, and later, when you haven't seen it in a long time. Standard names, like i and j for loop counters, and n for number is great, but what might an 'f' be?

Note that you need sqroot variable to be a double, not an int, and it needs math.h included.

You want modulo (remainder) arithmetic for this. The product of two other numbers, in determining if n is prime, is irrelevant, AFAIK.

how would you do it without the extra math functions because technically, we haven't learned any of that stuff in the class so far...like I said before all we have done is for loops, if statements, and a little bit of whiles....

here is a code that I tried to make up:

Code:

#include <stdio.h>
int main()
{
	int n,i,countp;
	printf("\nEnter value for n: ");
	scanf("%i", &n);
	
	while(countp<=n)
	{
		for(i=2; i=100; i++)	//i=100 is the limit I put...
		{
			if( %i==0)
			{
			//what statement do I put to make it go to the next number.
			}
			else
			{
				printf("%i", i);
				countp++;
			}	
		}
	}
return(0);
}

Above, my problem is that I do not know in the for loop, how exactly to implement the modulus operator (%) to check every number if it's a prime starting from i=2 until i=100 (the limit I put). I also don't think using i for the final printf is correct either....

I get confused with what you mean when you use ambiguous variable names, and put them into a program, perhaps not always in the right places.

I then have no idea what your intentions are, young man!

Let's look at a program from your original, that I know works, and see what can be done to simplify it to your class's level, so far:

Code:

#include <stdio.h>

int main()
{
        int howMany, i, isPrime, j, n; 
	printf("Enter the number of primes you want found: ");
	scanf("%d",&howMany);

	for(i=0, n = 1; i<howMany; i++)
	{  
            n++; 
            isPrime = 1;
	    for(j = 2; j <= n;  j++) 
            {
                if(n % j == 0)  
                   isPrime = 0;
            }             
            if(isPrime)  
               printf("\n%d", n); 
            else
               i--;
        }
	return(0);
}

So no more math.h include file needed, no more sqrt(), no more break statement. I can't test this atm, but tell me if it works and looks ok for you.

That's about as simple a way to do what you've asked, as I can manage.

yeah I think that's what also gets me confused, because I guess I always assume that some of the variables (like in the for loop should be only i, etc...)

also the code just hangs up....when you press enter after you enter a number, nothing happens and hangs up

yeah changing j<=n/2 works...

isPrime is a flag or switch, carrying the current state of the number being checked.

We start by assuming the number is a prime, by setting isPrime = 1 (true or

on). If n % any number other than itself or one == 0, then n is not a prime

number, so we set isPrime to 0. Since i is incremented with every run

through the outside loop, we need to decrement i by one every time it finds

a non-prime number.



If isPrime is still == 1 after all the mod tests, then it is a prime number,

so we print it.

oh ok, awesome, thanks for all the help, now I understand it!!

Code:

  while(Prime && Test < Root){

Test needs to be able to go up to the exact value of Root, if necessary (for example 9 is only composite due to being divisible to 3 which is exactly equal to sqrt(9)). It might also be necessary to pad the value of Root a bit to guard against floating-point error, for example by using sqrt(Target)+1 instead of sqrt(Target).

Originally Posted by abachler

Code:

    if(Prime % 2 == 0) return FALSE; // special case for 2 that speeds up the test

Not highly optimized, but this will be faster than checking every number.

Shouldn't this be

Code:

    if(Target % 2 == 0) return FALSE; // special case for 2 that speeds up the test

maverix