Prime Numbers, Modulus Operator Help

I'm working on homework for C programming class, and I can't figure this out. Question: "Write a program that obtains a number n from the user and prints the first n prime numbers, with one number printed per line"

So far we have learned for, if, while statements...

I have a for loop to calculate the nth prime numbers. But I'm not sure if "i<=n" should be the condition. Because if "i<=n", then when you want n=5 prime numbers, you won't get 5 numbers. underneath it is an if statement to determine if the number is prime or not. Then I was trying to figure out to display them, if using an IF statement would work.

please help, thanks

Code:

#include<stdio.h> int main() { int n,i,f=0; printf("Enter value for n: "); scanf("%i",&n); for(i=2;i<=n;i++) { if(n%i==0) f=1; if(f !=1) printf("%d",i); } return(0); }

Main returns int!

Quote:

I have a for loop to calculate the nth prime numbers. But I'm not sure if "i<=n" should be the condition. Because if "i<=n", then when you want n=5 prime numbers, you won't get 5 numbers.

It depends on what does i keep track of. If it keeps track of the number of prime numbers found so far, then for (i = 0; i < n; ++i) would be appropriate.

Also, you need to indent your code a little better.

i guess I should have two for loops. The first one to keep track of what is a prime number, then another for to keep track of the number of prime numbers.

I still need help to construct it

your program doesnt find the first n prime numbers, it finds the primes less than or equal to n. You need two loops, one that looks for the next prime, and one that keeps track of how many primes you have found.

You only need to check factors less than or equal to the square root of X to determine if X is prime.

If you are interested in primes, I have a file posted on my website that contains every 32 bit prime. You have to get the whole thing as its a compressed .bin file. The primes are there as DWORD's.

http://www.anthonyqbachler.com/32bit...bin.part01.rar
http://www.anthonyqbachler.com/32bit...bin.part02.rar
http://www.anthonyqbachler.com/32bit...bin.part03.rar
http://www.anthonyqbachler.com/32bit...bin.part04.rar
http://www.anthonyqbachler.com/32bit...bin.part05.rar
http://www.anthonyqbachler.com/32bit...bin.part06.rar
http://www.anthonyqbachler.com/32bit...bin.part07.rar
http://www.anthonyqbachler.com/32bit...bin.part08.rar
http://www.anthonyqbachler.com/32bit...bin.part09.rar
http://www.anthonyqbachler.com/32bit...bin.part10.rar
http://www.anthonyqbachler.com/32bit...bin.part11.rar
http://www.anthonyqbachler.com/32bit...bin.part12.rar
http://www.anthonyqbachler.com/32bit...bin.part13.rar
http://www.anthonyqbachler.com/32bit...bin.part14.rar
http://www.anthonyqbachler.com/32bit...bin.part15.rar

and if you need a recovery volume or 3 -

http://www.anthonyqbachler.com/32bit...bin.part01.rev
http://www.anthonyqbachler.com/32bit...bin.part02.rev
http://www.anthonyqbachler.com/32bit...bin.part03.rev

well, I guess my problem is trying to figure out how to link the first loop to the second loop.

pseudo code

Code:

get n count_of_primes = 0; current_number = 2; while(count_of_primes < n) { while(!is_prime(current_number )) current_number ++; output(current_number ); count_of_primes ++; }

is this C Programming? What is the ! in the code

Code:

while(!is_prime....)

well, my way of thinking about it was to first find prime numbers, then some how link the number of first prime numbers wanted, to those numbers I found then display them.

! is C operator

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

If n == n1*n2, then either n1 or n2 must be <= the square root of n (otherwise the product would be greater than n).

if I was to put n == n1*n2 to calculate if a prime or not, what would n1*n2 correspond to?

"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:

Quote:

Originally Posted by dcwang3

I'm working on homework for C programming class, and I can't figure this out. Question: "Write a program that obtains a number n from the user and prints the first n prime numbers, with one number printed per line"

So far we have learned for, if, while statements...

I have a for loop to calculate the nth prime numbers. But I'm not sure if "i<=n" should be the condition. Because if "i<=n", then when you want n=5 prime numbers, you won't get 5 numbers. underneath it is an if statement to determine if the number is prime or not. Then I was trying to figure out to display them, if using an IF statement would work.

please help, thanks

Code:

#include <stdio.h> #include <math.h> int main() { double sqroot; 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++; sqroot = sqrt(n); isPrime = 1; for(j = 2; j <= sqroot; j++) { if(n % j == 0) { isPrime = 0; --i; break; } } if(isPrime) printf("\n%d", n); } return(0); }

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.

Quote:

Originally Posted by dcwang3

if I was to put n == n1*n2 to calculate if a prime or not, what would n1*n2 correspond to?

My point is that checking whether n is prime is equivalent to checking whether it has a nontrivial factor or not, and if it does, one of them has to be <= the square root of n, so those are the only numbers you have to check.

Quote:

Originally Posted by dcwang3

if I was to put n == n1*n2 to calculate if a prime or not, what would n1*n2 correspond to?

You can't put "n==n1*n2", at least if you mean what I think you mean. We're just saying that if n is composite, then n equals n1*n2 for some n1 and n2 that we don't care about. To find if there are such numbers, that's why we do the trial division with the %.

Quote:

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.

Quote:

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

Quote:

Originally Posted by Adak

I can't test this atm, but tell me if it works and looks ok for you.

It is not ok at least on 2 reasons:

2 is always missed (but it is prime number)

any number is reported as not-prime due to

j<=n condition (Think what you get when j == n) - and this is the reason why there is no output from the program.

it should be
j<= n/2 at least

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

here are my comments just to make sure I understand what exactly each part does....
please correct me or add something if needed, thanks

ALSO, what is the "isPrime =1, and isPrime=0" correspond to, what does that do?

Sorry for asking so many questions but I'm just trying to understand this. THANKS!!!

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++) //keeps track of how many prime numbers I found { n++; //n=n+1, this is the current number testing if prime isPrime = 1; // not sure what this does for(j = 2; j <= n/2; j++) // calculates if a prime number or not { if(n % j == 0) // calculates prime number ie. 2%2= 0. ? isPrime = 0; // thus if zero, then isPrime? } if(isPrime) //if isPrime, then it prints the number? printf("\n%d", n); else // if not printed, then it decreases the prime i--; // numbers found (essentially does not add one) } return(0); }

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:

#include <windows.h> #include <math.h> BOOL IsPrime(DWORD Target){ DWORD Root , Test; BOOL Prime = TRUE; if(Prime % 2 == 0) return FALSE; // special case for 2 that speeds up the test Root = sqrt(Target); Test = 3; while(Prime && Test < Root){ if(Target % Test == 0) Prime = FALSE; Test += 2; } return Prime; }

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

Quote:

if(Prime % 2 == 0)

too optimized

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).

you are correct, it should have been -

Code:

while(Prime && Test <= Root){

As for padding, personally I use a much faster although more convoluted method of updating Root that bypasses the slow SQRT() function. Since im assuming the teacher will not enter some obtusely large number for the count of primes to find ( like 200 million) runtime shouldnt be an issue.

Quote:

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

Quote:

Originally Posted by abachler

As for padding, personally I use a much faster although more convoluted method of updating Root that bypasses the slow SQRT() function. Since im assuming the teacher will not enter some obtusely large number for the count of primes to find ( like 200 million) runtime shouldnt be an issue.

You don't need to use sqrt() to do the optimization.

Code:

result = possible_prime / possible_factor; if(result < possible_factor) { /* Obviously, we've crossed the square root at this point. */ }

HEY you've been looking at my notes :D

Actually I just do that step to determine if I need to Root++

Code:

if(Prime / Root > Root) Root+=2;

different implementation, btu the same core method. The reason I increase root by 2 is we will only be checking odd number factors anyway.

Quote:

Originally Posted by vart

too optimized

then try this -

Code:

if(!(Prime & 1)) return FALSE;

Quote:

Originally Posted by abachler

then try this -

Code:

if(!(Prime & 1)) return FALSE;

it was a joke, checking Prime in any way will do you no good here... As was said - you need to test the value of Target

oh gawd, yeah i totally missed that one, it shodul be

Code:

if(!(Target & 1)) return FALSE;

thanks for catching that nub mistake vart :D

BTW, for anyone that tried to D/L the primes in the last few days and got a service message, the site is back up and running. Sorry I forgot to pay the bill :rolleyes: