Thread: Prime Numbers, Modulus Operator Help

  1. #1
    Registered User
    Join Date
    Feb 2008
    Posts
    116

    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("&#37;i",&n);
    
    	for(i=2;i<=n;i++)
    	{
    	if(n%i==0)
    	f=1;
    	
    	if(f !=1)
    	printf("%d",i);
    
    	}
    
    	
    	return(0);
    }
    Last edited by dcwang3; 02-05-2008 at 11:06 AM.

  2. #2
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Main returns int!
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  3. #3
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    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.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  4. #4
    Registered User
    Join Date
    Feb 2008
    Posts
    116
    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
    Last edited by dcwang3; 02-05-2008 at 11:24 AM.

  5. #5
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,195
    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

  6. #6
    Registered User
    Join Date
    Feb 2008
    Posts
    116
    well, I guess my problem is trying to figure out how to link the first loop to the second loop.

  7. #7
    Hurry Slowly vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,788
    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 ++;
    }
    All problems in computer science can be solved by another level of indirection,
    except for the problem of too many layers of indirection.
    – David J. Wheeler

  8. #8
    Registered User
    Join Date
    Feb 2008
    Posts
    116
    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.

  9. #9
    Hurry Slowly vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,788
    ! is C operator
    All problems in computer science can be solved by another level of indirection,
    except for the problem of too many layers of indirection.
    – David J. Wheeler

  10. #10
    Registered User
    Join Date
    Feb 2008
    Posts
    116
    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&#37;j or visa versa
    Last edited by dcwang3; 02-05-2008 at 12:36 PM.

  11. #11
    Registered User
    Join Date
    Sep 2006
    Posts
    835
    If n == n1*n2, then either n1 or n2 must be <= the square root of n (otherwise the product would be greater than n).

  12. #12
    Registered User
    Join Date
    Feb 2008
    Posts
    116
    if I was to put n == n1*n2 to calculate if a prime or not, what would n1*n2 correspond to?

  13. #13
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    "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 View Post
    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("&#37;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.
    Last edited by Adak; 02-05-2008 at 01:31 PM.

  14. #14
    Registered User
    Join Date
    Sep 2006
    Posts
    835
    Quote Originally Posted by dcwang3 View Post
    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.

  15. #15
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Quote Originally Posted by dcwang3 View Post
    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 &#37;.
    Last edited by tabstop; 02-05-2008 at 01:39 PM. Reason: fixed

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Logical errors with seach function
    By Taka in forum C Programming
    Replies: 4
    Last Post: 09-18-2006, 05:20 AM
  2. prime numbers, counters, help!
    By vege^ in forum C++ Programming
    Replies: 1
    Last Post: 03-10-2003, 04:32 PM
  3. More Prime Numbers
    By mmuhlenb in forum C Programming
    Replies: 3
    Last Post: 02-21-2003, 10:06 AM
  4. Prime numbers
    By Lazy Student in forum C Programming
    Replies: 12
    Last Post: 05-14-2002, 05:53 AM
  5. Homework help
    By Jigsaw in forum C++ Programming
    Replies: 2
    Last Post: 03-06-2002, 05:56 PM