C++ prime number program help

[djbsabkcb]

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
#include

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;
}
}
}
}

[winbatch]

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]

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

[djbsabkcb]

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

[djbsabkcb]

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

[winbatch]

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

[djbsabkcb]

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.

[winbatch]

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]

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

[inoxmum]

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]

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

[inoxmum]

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]

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]

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;
}
}

[szkhanctg]

#include

using namespace std;
void main()

{
int i,j;
for(i=2;i<=100;)
{
if(i==2)
{
cout<

[Skeen]

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!