C++ prime number program help

Question

djbsabkcb 0 Junior Poster in Training

19 Years Ago

Below is my code for printing prime numbers up to a given input by user. However, my calculations are not working correctly and my output is printing twice. Any idea? :sad:

#include <iostream>
#include <cmath>

using namespace std;
void prime_num(int);

int main()
{



        cout << " Enter a number and I will generate the prime numbers up to that number:  ";
        int num = 0;
        cin >> num;

        prime_num(num);
}



        void prime_num( int num)
        {
                int check_prime = 0;

                for ( int i = 0; i <= num; i++)
                {
                        check_prime = 1;

                        for ( int j = 2; j <= i/2; j++)
                        {
                                if ( i % j == 0 )

                                        check_prime = 0;

                                if ( check_prime != 0 )
                                {
                                        cout << i << endl;
                                }
                        }
                }
        }

c++

Edited 11 Years Ago by TrustyTony because: fixed formating

13 Contributors
18 Replies
2K Views
8 Years Discussion Span
Latest Post 10 Years Ago Latest Post by duskoKoscica

winbatch 7 Posting Pro in Training

19 Years Ago

Here's what I went with. Note you want to do a break if you find out it's divisible as there is no point in checking all the numbers beyond it for divisibility..

#include <iostream>
using namespace std;
void prime_num(int);
int main()
{
cout << " Enter a number and I will generate the prime numbers up to that number: ";
int num = 0;
cin >> num;
prime_num(num);
}
 
void prime_num( int num)
{
		bool isPrime=true;
		for ( int i = 0; i <= num; i++)
		{
				for ( int j = 2; j <= num; j++)
				{
						if ( i!=j && i % j == 0 )
						{
						  isPrime=false;
						  break;
						}
				}
				if (isPrime)
				{
				  cout <<"Prime:"<< i << endl;
				}
				isPrime=true;
		}
}

Enter a number and I will generate the prime numbers up to that number: 100
Prime:1
Prime:2
Prime:3
Prime:5
Prime:7
Prime:11
Prime:13
Prime:17
Prime:19
Prime:23
Prime:29
Prime:31
Prime:37
Prime:41
Prime:43
Prime:47
Prime:53
Prime:59
Prime:61
Prime:67
Prime:71
Prime:73
Prime:79
Prime:83
Prime:89
Prime:97

Note you can check your results here:
http://www.utm.edu/research/primes/lists/small/1000.txt

zyruz 0 Junior Poster in Training

19 Years Ago

It is printing the number multiple times, becuse of:

for ( int j = 2; j <= i/2; j++)
        {
            if ( i % j == 0 )
            {
                check_prime = 0;
            }
            
            if ( check_prime != 0 )
            {
                cout << i << endl;
            }
        }

here you are printing out the number when check prime != 0.
but untill i%j == 0 the program are going to ouput that the number is prime, even when it aint.
this is bad design, and I think you need to rewrite your function.

check out: http://www.daniweb.com/techtalkforums/thread27064-prime.html

winbatch 7 Posting Pro in Training

19 Years Ago

So Picky ;). As you wish:

#include <iostream>
using namespace std;
void prime_num(int);
int main()
{
cout << " Enter a number and I will generate the prime numbers up to that number: ";
int num = 0;
cin >> num;
prime_num(num);
}
 
void prime_num( int num)
{
		bool isPrime=true;
		for ( int i = 2; i <= num; i++)
		{
				for ( int j = 2; j <i; j++)
				{
						if ( i % j == 0 )
						{
						  isPrime=false;
						  break;
						}
				}
				if (isPrime)
				{
				  cout <<"Prime:"<< i << endl;
				}
				isPrime=true;
		}
}

Enter a number and I will generate the prime numbers up to that number: 150
Prime:2
Prime:3
Prime:5
Prime:7
Prime:11
Prime:13
Prime:17
Prime:19
Prime:23
Prime:29
Prime:31
Prime:37
Prime:41
Prime:43
Prime:47
Prime:53
Prime:59
Prime:61
Prime:67
Prime:71
Prime:73
Prime:79
Prime:83
Prime:89
Prime:97
Prime:101
Prime:103
Prime:107
Prime:109
Prime:113
Prime:127
Prime:131
Prime:137
Prime:139
Prime:149

winbatch 7 Posting Pro in Training

19 Years Ago

I know what you mean...

By the way, no need to quote the entire previous posting when putting a reply (only the relevant piece)..

Pcyther 0 Newbie Poster

19 Years Ago

Hello My friend, I do not know if my response will be in time for you but here is a master code for finding all prime numbers up to any number 'x' that you input...

# include <cmath>          // This library enable the use of sqrt.
# include <iostream>
using namespace std;

void primenum(long double);     // Prototype...
int c = 0;

int main()
{
long double x = 0;
cout<<"\n This program will generate all prime numbers up to the"
    <<"\n number you have entered below...\n";
cout<<"\n Please enter a number: ";
cin>> x;

cout<<"\n Here are all the prime numbers up to "<<x<<".\n";
primenum(x);            //function invocation...
cout<<endl<<"\nThere are "<<c
    <<" prime numbers less than or equal to "<<x<<".\n\n";

return 0;
}

// This function will determine the primenumbers up to num.
void primenum(long double x)
{
    bool prime = true;                  // Calculates the square-root of 'x'
    int number2;
     number2 =(int) floor (sqrt (x));

    for (int i = 1; i <= x; i++){       
        for ( int j = 2; j <= number2; j++){
            if ( i!=j && i % j == 0 ){      
                prime = false;
                break;
            }
        }
        if (prime){
            cout <<"  "<<i<<" ";
            c += 1;
        }
        prime = true;
    }
}

// In you need any explanation for any parts of this program send me a message and i will reply as soon as i can...

Reply to this topic

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.

djbsabkcb 0 Junior Poster in Training · Answer 1 · 2005-07-17T04:39:31+00:00

I see what you are saying but that still isn't right because 1 is not a prime number

djbsabkcb 0 Junior Poster in Training · Answer 2 · 2005-07-17T04:40:08+00:00

Here's what I went with. Note you want to do a break if you find out it's divisible as there is no point in checking all the numbers beyond it for divisibility..
#include <iostream>
using namespace std;
void prime_num(int);
int main()
{
cout << " Enter a number and I will generate the prime numbers up to that number: ";
int num = 0;
cin >> num;
prime_num(num);
}
 
void prime_num( int num)
{
		bool isPrime=true;
		for ( int i = 0; i <= num; i++)
		{
				for ( int j = 2; j <= num; j++)
				{
						if ( i!=j && i % j == 0 )
						{
						  isPrime=false;
						  break;
						}
				}
				if (isPrime)
				{
				  cout <<"Prime:"<< i << endl;
				}
				isPrime=true;
		}
}
Enter a number and I will generate the prime numbers up to that number: 100
Prime:1
Prime:2
Prime:3
Prime:5
Prime:7
Prime:11
Prime:13
Prime:17
Prime:19
Prime:23
Prime:29
Prime:31
Prime:37
Prime:41
Prime:43
Prime:47
Prime:53
Prime:59
Prime:61
Prime:67
Prime:71
Prime:73
Prime:79
Prime:83
Prime:89
Prime:97
Note you can check your results here:
http://www.utm.edu/research/primes/lists/small/1000.txt

I see what you are saying but that still isn't right because 1 is not a prime number

djbsabkcb 0 Junior Poster in Training · Answer 3 · 2005-07-17T05:11:01+00:00

So Picky ;). As you wish:
#include <iostream>
using namespace std;
void prime_num(int);
int main()
{
cout << " Enter a number and I will generate the prime numbers up to that number: ";
int num = 0;
cin >> num;
prime_num(num);
}
 
void prime_num( int num)
{
		bool isPrime=true;
		for ( int i = 2; i <= num; i++)
		{
				for ( int j = 2; j <i; j++)
				{
						if ( i % j == 0 )
						{
						  isPrime=false;
						  break;
						}
				}
				if (isPrime)
				{
				  cout <<"Prime:"<< i << endl;
				}
				isPrime=true;
		}
}
Enter a number and I will generate the prime numbers up to that number: 150
Prime:2
Prime:3
Prime:5
Prime:7
Prime:11
Prime:13
Prime:17
Prime:19
Prime:23
Prime:29
Prime:31
Prime:37
Prime:41
Prime:43
Prime:47
Prime:53
Prime:59
Prime:61
Prime:67
Prime:71
Prime:73
Prime:79
Prime:83
Prime:89
Prime:97
Prime:101
Prime:103
Prime:107
Prime:109
Prime:113
Prime:127
Prime:131
Prime:137
Prime:139
Prime:149

thanks, that is correct.

its funny you can sit in front of this screen and try to debug for hours and once you figure it out it was something small to begin with. Very frustrating.

inoxmum -1 Newbie Poster · Answer 4 · 2007-03-26T20:26:40+00:00

Hello My friend, I do not know if my response will be in time for you but here is a master code for finding all prime numbers up to any number 'x' that you input...

# include <cmath>          // This library enable the use of sqrt.
# include <iostream>
using namespace std;
 
void primenum(long double);     // Prototype...
int c = 0;
 
int main()
{
long double x = 0;
cout<<"\n This program will generate all prime numbers up to the"
    <<"\n number you have entered below...\n";
cout<<"\n Please enter a number: ";
cin>> x;
 
cout<<"\n Here are all the prime numbers up to "<<x<<".\n";
primenum(x);            //function invocation...
cout<<endl<<"\nThere are "<<c
    <<" prime numbers less than or equal to "<<x<<".\n\n";
 
return 0;
}
 
// This function will determine the primenumbers up to num.
void primenum(long double x)
{
    bool prime = true;                  // Calculates the square-root of 'x'
    int number2;
     number2 =(int) floor (sqrt (x));
 
    for (int i = 1; i <= x; i++){       
        for ( int j = 2; j <= number2; j++){
            if ( i!=j && i % j == 0 ){      
                prime = false;
                break;
            }
        }
        if (prime){
            cout <<"  "<<i<<" ";
            c += 1;
        }
        prime = true;
    }
}

// In you need any explanation for any parts of this program send me a message and i will reply as soon as i can...

very very very nice programmmm......
and thanks for this .....

John A 1,896 Vampirical Lurker Team Colleague · Answer 5 · 2007-03-27T05:45:21+00:00

John A 1,896 Vampirical Lurker

17 Years Ago

You bumped a 2 year-old thread to say that? ^_^

inoxmum -1 Newbie Poster · Answer 6 · 2007-03-27T10:13:59+00:00

You bumped a 2 year-old thread to say that? ^_^

old is always gold my dear friend...
it helped me a lot as i am not a full fledged developer.......
thanks again

ronan001 -2 Newbie Poster · Answer 7 · 2007-05-11T04:05:23+00:00

Those other solutions are abit too complex?!!

This counts all your prime nums from 0 to 100

#include <iostream>
int main()
{
int freq=0;
for(int i=1;i<100;i++){

int isZero=0;
for (int j=1;j<i;j++)
{
if (i%j==0)
isZero++;
}
if (isZero ==1)
{
freq++;
}
}
std::cout << "The Frequecy of Prime Number is " << freq << std::endl;

return 0;
}

hidasip 0 Newbie Poster · Answer 8 · 2007-09-24T01:10:02+00:00

Here is a translation to normal C ,( if anyone interested), i have changed a couple things, you have to give a min and a max value and it will list the prime numbers between the two given numbers.

# include "stdio.h"



void prim_max(max,min);
int main()
{


int max , min = 0;
int k;


printf(" max: ");
scanf("%d",&max);


printf(" min: ");
scanf("%d",&min);



printf("[%d:\n",min);



prim_max(max,min);


printf("%d]\n",max);


scanf("%d",&k);
}


void prim_max(max,min)
{
int i,j;
int prime = 1;


for (i = min; i <= max; i++)
{
for ( j = 2; j < i; j++)
{
if ( i % j == 0 )
{
prime = 0;
break;
}
}
if (prime)
{
printf("%d\n",i);
}
prime = 1;
}
}

alwaysbeginner -4 Newbie Poster · Answer 9 · 2010-01-28T01:31:43+00:00

#include<iostream>

using namespace std;
void main()

{
int i,j;
for(i=2;i<=100;)
{
if(i==2)
{
cout<<i;
cout<<"\n";
goto p;
}
for(j=2;j<i;)

{

if((i%j)==0)

{

goto p;

}

j++;

}

cout<<i;
cout<<"\n";
p:
i++;
}
getchar();
}

What a waste of effort. Over 2 years late, and no flippin' code tags!

Skeen 0 Junior Poster in Training · Answer 10 · 2010-01-28T01:51:57+00:00

So I've been testing these algorithms, and really, they're SO slow >.<, I myself made a prime number calculator, when I needed to regenerate prime numbers for some RSA encryption, however, I used this program; It's able to find all the prime numbers from 3-50.000.000 in about 2½second.

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

#define TYPE register unsigned int

int main()
{
    TYPE n, p=1, i=0, j, count=1;
    register bool done;
    register clock_t Time;

    printf("250.000.000 = ~500mb ram..\n\n   Calculate primes up to: ");
    scanf("%d", &n);
    printf("\nCalculating...\n");
    n /= 2;       
    
    TYPE *buffer = (unsigned int*)malloc(n * sizeof(unsigned int));  
    if (buffer == 0)
    {
        printf("Could not allocate RAM!\n\n");
        return 0;
    }
    Time = clock();
    
    for (i=0; i != n; i++)
        {
        buffer[i] = i*2+3;
        }
        
    i = 0;
    
    while (1)
    {
        done = true;
        for (j=i; j < n; j++)
        {
            if (buffer[j] > p)
            {
                p = buffer[j];
                done = false;
                break;
            }
        }
    i = j+1;
    if (!done)
       {
       while (j+p < n) buffer[j+=p] = 0;
       } 
    else 
       {
       break;
       }         
    }
    
    for (unsigned int i=0; i != n; i++)
    {
        if (buffer[i])
        {
            count++;
        }
    }
    
    printf("\n...Calculation done :)\n %d Primenumbers found in %1.3f seconds!\n", count, (clock()-Time)/(float)CLOCKS_PER_SEC);
    free(buffer);
    
    return 0;
}

And it's just a based upon the simple (and slow) Sieve of Eratosthenes algorithm! If you're to write anything useful, you should use the Sieve of Atkin algorithm!

eriknyquist 0 Newbie Poster · Answer 11 · 2012-06-24T12:35:25+00:00

This one is a lot simpler. It calculates all the factors of i, sums them, and dumps them into "binsum". If the value of binsum is equal to i + 1 (that is, if the only factors for that number are itself and 1), then the number is prime and it gets printed.
This one will print all prime numbers between 1 and 10,000.

#include <iostream>
using namespace std;
int main()
{  
    int binsum = 0;

    for(int i = 2; i <= 10000; i++) {


        for(int j = 1; j <= i; j++)
            if((i%j) == 0) binsum += j; 

        if (binsum == i + 1) cout << i << "\n";
        binsum = 0;
        }

    }

irum.nageen.3 -6 Newbie Poster · Answer 12 · 2013-09-23T19:44:18+00:00

//Prime Numbers generation in C++
//Using for loops and conditional structures
#include <iostream>
using namespace std;

int main()
{
    int a = 2;       //start from 2
    long long int b = 1000;     //ends at 1000

    for (int i = a; i <= b; i++)
    {

     for (int j = 2; j <= i; j++)
     {
        if (!(i%j)&&(i!=j))    //Condition for not prime
            {
                break;
            }

        if (j==i)             //condition for Prime Numbers
            {
                  cout << i << endl;

            }
     }
    }
}

duskoKoscica 0 Newbie Poster · Answer 13 · 2014-01-12T08:46:02+00:00

Well, small thougt form number theory.
Every prime number greater than 3 is of 6n+1 or 6n-1 form, the oposite way thos not fly.
The improvement is try to divide number by 6 and if you have like 5 or 1 remaning you have potential prime number.
I have not read this article all the way, but I just like this thing.
When you divide the number it could this trick could be used, or perhaps not, the qustion is NoW!