Prime Numbers

This is a discussion on Prime Numbers within the C++ Programming forums, part of the General Programming Boards category; I'm not really sure how to phrase this, so please bear with me. I need to write a program, that ...

  1. #1
    Registered User
    Join Date
    Dec 2001
    Posts
    11

    Question Prime Numbers

    I'm not really sure how to phrase this, so please bear with me. I need to write a program, that amongst other things, uses an "equation" (not just spitting out "1, 2, 3, 5....") to display 30 prime numbers. I don't want to "cheat" like I'm seeing some other students doing, but I'm not sure where to start. If anyone has any ideas on how to do this or where to look, I'd really appreciate it.
    The only thing I can think of doing so far is testing a heck of alot of numbers by dividing by the numbers 2-11 with/without a remainder (as long as the divisor isn't the one I'm using to test), but if I do that I'm not sure how to set up the loop to display 30 numbers and just not test 30 numbers. I hope this makes sense, and ANY help/examples anyone could provide would be helpful!!!!!

    Christina

  2. #2
    Registered User
    Join Date
    Feb 2002
    Posts
    591
    Your idea sounds about right. Try to build some code around it or search the board. It have been answeared many times before.

  3. #3
    Davros
    Guest
    Technically speaking, there is no known (at least accepted) equation for spitting out prime numbers, although I think someone recently suggested an order 25 polynomial equation.

    Are you talking about an equation, or an algorithm?

  4. #4
    Registered User
    Join Date
    Dec 2001
    Posts
    11
    It was phrased "equation" only to prevent us from just spitting out what we already know without allowing the program to do the work...does that clear it up?

  5. #5
    Just because ygfperson's Avatar
    Join Date
    Jan 2002
    Posts
    2,493
    so, in other words, the program find prime numbers in any way, but it cannot just have
    Code:
    printf("2, 3, 5, etc...");
    it must figure it out?
    like Barjor said, it's been answered many times before. try a brute force method. or the sieve of erethosenese... whatever that spelling was.

  6. #6
    Davros
    Guest
    Then its an algorithm. (I was't being pedantic)

    I suggest that you create a function to fill out an array of 30 integers - your prime number results.

    Your function should run around a loop incrementing a count by two each time, starting from one (i.e. so you only get odd numbers*).

    For each count (n), you should run through divisor tests from 3 to the square root of n (there's no point in testing divisors above the square root). If no test divisor fits into n without a remainder, add n to your result array and continue the increment until you fill all 30 elements.

    * The values 1 & 2 may be considered prime numbers, but because these are exceptions, I would reckon it would be acceptable to hard code these as results if required.

    When your function returns, output the results to screen.

    Question? Is your algorithm really a true algorithm? I.e. can we prove that it will return in a finite time?

  7. #7
    Registered User
    Join Date
    Apr 2002
    Posts
    200
    Technically, 1 is not prime.

  8. #8
    In The Light
    Join Date
    Oct 2001
    Posts
    598
    howdy,
    ive been out of school for a long time BUT this
    although I think someone recently suggested an order 25 polynomial equation.
    seems a bit extreme to me.

    itld reaches for college calculus book.

    M.R.
    I don't like you very much. Please post a lot less.
    Cheez
    *and then*
    No, I know you were joking. My point still stands.

  9. #9
    Davros
    Guest
    > seems a bit extreme to me.

    Well, it depends on what you want to do. Generating a lot of prime numbers quickly is important if you want to break an RSA algorithm. The problem with generate & test algorithms is that they get progressively slower the larger the number. This is one of the reasons why prime numbers are so important in encryption.

    If you could have an equation that looked like this:

    a = f(n)

    where a is always prime. That would be quite a break through.

  10. #10
    Registered User
    Join Date
    Dec 2001
    Posts
    28
    Ok. I don't know if you just want the code, or if you want to do it yourself. If you want the code, look down, if you want to figure it out yourself, look up the Sieve of Eratosthenes.

    Code:
    #include <iostream.h>
    #define arraysize 30  
    //defining makes code more readable than just putting a sentinal in
    
    void main()
    {
    	int primes[arraysize]={1}; //#1 is set to 1, everything else is still 0
    
    	int pause=0;  //garbage variable, used to stop the text from
    				//scrolling for a moment.
    
    	for (int i = 2; i <= arraysize/2; i++) 
    	{ 
    		for (int j = 2; (j * i) < arraysize; j++) 
    		{ 
    		primes[j * i] = 1; //all non-primes are set to one
    		} 
    	} 
    
    	for (i = 1; i < arraysize; i++) 
    	{ 
    		if (primes[i] == 0)
    	    cout<< i << " is a prime number." << endl; 
    
    		if ((i % 50) == 0)
    		{
    			cout << "Enter any number to continue."<<endl;
    			cin >> pause;
    		}
    	} 
    }
    Last edited by Will; 04-30-2002 at 03:33 PM.

  11. #11
    Registered User
    Join Date
    Dec 2001
    Posts
    11
    Well, if I had done a more thorough search in Borland's help, I would have been all set. This is what I came up with...

    {
    RichEdit1->Lines->Insert(0,1);
    const int sievesize = 125;
    vector<int,allocator<int> > sieve(sievesize, 1);

    for (int i = 2; i * i < sievesize; i++)
    if (sieve[i])
    for (int j = i + i; j < sievesize; j += i)
    sieve[j] = 0;

    for (int j = 2; j < sievesize; j++)
    if (sieve[j])
    RichEdit1->Lines->Add(j++);
    }

    Now I just need to be a bit more intellegent to get this to sort in descending order...oh boy.

    For now I'll move on to writing the code for the Fibonacci Sequence.

    Just one more week of this and I'll be done !!! LOL

    Thanks for your help!!

  12. #12
    Unregistered Leeman_s's Avatar
    Join Date
    Oct 2001
    Posts
    753
    Code:
    #include "iostream.h"
    #include "iomanip.h"
    
    int main()
    {
    	const int MAX=100;
    	long primes[MAX]={2,3,5};
    	long trial=5;
    	int count=3;
    	int found=0;
    
    
    	do
    	{
    		trial+=2;
    		found=0;
    		for(int i=0;i<count;i++)
    		{
    			found=(trial % *(primes + i)) == 0;
    
    			if(found)
    				break;
    		}
    		if (found==0)
    			*(primes + count++) = trial;
    	}while(count<MAX);
    
    	for(int i = 0;i < MAX;i++)
    	{
    		if(i % 5 == 0)
    			cout<<endl;
    		cout<<setw(10)<<*(primes + i);
    	}
    	cout<<endl;
    	return 0;
    }
    hows that?

  13. #13
    Registered User
    Join Date
    Jan 2002
    Posts
    63
    i do believe this is where the mod math function should be used
    SS3X

  14. #14
    Registered User Liam Battle's Avatar
    Join Date
    Jan 2002
    Posts
    114
    if you want to estimate a set of numbers you can simply use the mathematical formula by Bernoulli,
    if you use the formula :

    z
    __ = B0 + B1^z + B2z^2 Bkz^k
    -------- + ... = E ---------
    e^z -1 2! k>0 k!

    that will get you an approximation based on a set of numbers, just apply that formula to your algorithm..

    or you can use Eulers General Formula.

    if anyone else goes to stamford they will know what im talking about...

    if not sorry...

    ugh i just looked at the post and it formated the formula wrong on the screen... sorry
    LB0: * Life once school is done
    LB1: N <- WakeUp;
    LB2: N <- C++_Code;
    LB3: N >= Tired : N <- Sleep;
    LB4: JMP*-3;

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. Replies: 18
    Last Post: 11-04-2005, 01:41 PM
  3. prime numbers, counters, help!
    By vege^ in forum C++ Programming
    Replies: 1
    Last Post: 03-10-2003, 03:32 PM
  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, 04:56 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21