C++ Program.....NEED HELP fast..due MOnday.. [Archive]

C++ Im dead

11-02-2002, 08:01 PM

This is the program....

An integer is said to be prime if it is divisible by only 1 and itself. For example 2,3,5 and 7 are prime, but 4,6,8 and 9 are not.

---A) Write a function that determines weather a number is prime.

---B) Use this function in a program that determines and prints all the prime numbers between 1 and 10,000. HOw many of these 10,000 numbers do you really have to test before being sure that you have found all the primes.

---C) Initially, you might think that n/2 is the upper limit for which you must test to see whether a number is prime, but you need only go as high as the square root of n. WHY? Rewrite a program and run it both ways. Estimate the performance improvement.

........PLEASE HELP!!!!!!!! I was able to do every other program for the exception of this one........and this is the most important of them all..............HELP!!!!!!!!!!!!!!!!!!!!!!

scanez

11-02-2002, 08:33 PM

1. Please do not crosspost.

2. What problems are you having exactly?

3. Prime numbers rule :)

C++ Im dead

11-02-2002, 08:39 PM

I'm having problem with the entire program.......but esp. with the function.......can't get the function....!!!!!!!

scanez

11-02-2002, 08:44 PM

Well as you said, an integer is prime if it is divisible only by 1 and itself. So first, any even integer greater than 2 cannot be prime. Now, for any odd number, see if it is divisible by any odd integer less than it- if so the integer is not prime, if not it is prime. Write a function that does this ;)

monkeyboi

11-02-2002, 08:45 PM

i'll give u an example for question a)

int prime(int num)
{

int i, p = 1;

for (i = 2; i < num; i++)
{

if ((num % i) == 0)
{
cout <<"Not Prime Number"<<endl;
p = 0;
}
}

if ( p = 1)
{
cout<<"It's a Prime Number" <<endl;
}

}

didn't compile to code but i'm pretty sure it will work....

scanez

11-02-2002, 08:45 PM

NO! Don't give him the answer! :mad:

monkeyboi

11-02-2002, 08:46 PM

ahhh change the int prime(int num) to void prime(int num)

scanez

11-02-2002, 08:48 PM

Oh yeah, then for part b you just run the program on the first 10,000 integers. For part c you just modify the program to only check to see if the integer is divisible by any integers <= it's square root.

monkeyboi

11-02-2002, 08:48 PM

scanez jux only a small example man.. maybe he is really stuck...

i kno how it feel when u completely stuck on some project and don't kno where to start...

cnjohnson

11-02-2002, 09:01 PM

Originally posted by C++ Im dead
I'm having problem with the entire program.......but esp. with the function.......can't get the function....!!!!!!!

Well, you could try something like this:

if ( prime_number == 2 )
{
return (prime_number);
}

for( ; ; )
{
prime_number += 2;
int prime_found = 1;
int max_times = ( prime_number / 2 ); // or use the sqrt
for ( int i = 3; i < max_times; ++i )
{
if ( ( ( prime_number / i ) * i ) == prime_number )
{
prime_found = 0;
break;
}
}
if ( prime_found )
break;
}

TacKat

11-02-2002, 09:27 PM

C) Initially, you might think that n/2 is the upper limit for which you must test to see whether a number is prime, but you need only go as high as the square root of n. WHY?

If 2 divides n, then you know two factors, 2 and n/2. If 3 divides n, then you know 3 and n/3 are factors. The larger factor keeps getting smaller, but notice how it does it.

Look at some examples. Does 25 divide 27? It's quite clear it doesn't. Does 514736 divide 546534? Again it's clear it doesn't, but think about what you are using to decide this so easily.

Does 54 divide 546534? The answer is not obvious, so what makes it different from the other two cases?

C++ Im dead

11-02-2002, 10:26 PM

Originally posted by scanez
NO! Don't give him the answer! :mad:

NO! YES!! Do give me the answer...:( please im very:confused:

mingshun

11-03-2002, 09:58 AM

Originally posted by C++ Im dead

---C) but you need only go as high as the square root of n.

I got this from a Math friend.
Square root that number, run a loop from 2 to square root of that number, divide that number with this index and see if you get an integer.

i.e: n = 10000, sq rt of this is 100
Then from divide 10000 by 2, if the result is an integer, print "Not prime" and exit. Else divide 10000 by 3, check the result to see if it is integer, if no, divide 10000 by 4 .... until by 100.

TacKat

11-03-2002, 10:44 AM

Originally posted by mingshun
Else divide 10000 by 3, check the result to see if it is integer, if no, divide 10000 by 4 .... until by 100.

You don't really need to check if it's divisible by 4, since it would also be divisible by 2 (and you already know that it's not).

In fact, you only need to see if it is divisible by primes, but unless you have a list of primes handy or you need to check a lot of numbers, it's not that much worse to just check all the odds.

mingshun

11-03-2002, 12:41 PM

Originally posted by TacKat
You don't really need to check if it's divisible by 4, since it would also be divisible by 2 (and you already know that it's not).

In fact, you only need to see if it is divisible by primes, but unless you have a list of primes handy or you need to check a lot of numbers, it's not that much worse to just check all the odds.

Hmmm, but I think that will be a lot more complicated to write. How do we have a brunch of prime numbers ready at the first place?

Hence, I think eventually, the most generic way to solve this problem so far is to divide it until it reaches the sqrt of that number (take the floor of it if the sqrt does not give an integer). At least, the big O is logN now rather than N.

Ludootje

11-03-2002, 01:07 PM

Originally posted by scanez
NO! Don't give him the answer! :mad:
Why not? :)

C++ Im dead

11-03-2002, 01:43 PM

Originally posted by Ludootje
Why not? :)

Yea WHY not??? I only have 23 hours left.........and don't have nothing YET....:(

mingshun

11-03-2002, 01:51 PM

Originally posted by C++ Im dead
Yea WHY not??? I only have 23 hours left.........and don't have nothing YET....:(

Ok ok, I try to code but I won't compile it ...

#include <math.h>
#include <stdio.h>

int testno = 10000;

/* num is the number that you wanna test.
return 0: it is not a prime number
return 1: it is a prime number
*/

int isPrime (int num) {

int limit = (int) sqrt (num);
int i = 0;

for (i = 2; i <= limit; i++)
if (num % i == 0) return 0;

return 1;
}

main () {
if (isPrime (testno)) cout << "testno is a prime number." << endl;
else cout << "testno is not a prime number."<< endl;
}

Compile this with -lm option and debug it yourself if neccessary.

TacKat

11-03-2002, 01:59 PM

Originally posted by mingshun How do we have a brunch of prime numbers ready at the first place?

Well you just do it in reverse. Every number not divisible by 2 up to 2^2 is prime; ie 3. Then every number not divisible by 2 or 3 up to 3^2=9 is prime; ie 5,7. Every number up to 7^2=49 not divisible by 2,3,5, or 7 is prime, etc etc.

It's only slightly more complicated in that you read your potential divisors in from a file instead of generating them in a loop.

Hence, I think eventually, the most generic way to solve this problem so far is to divide it until it reaches the sqrt of that number (take the floor of it if the sqrt does not give an integer). At least, the big O is logN now rather than N.

Yes, dividing up to the sqrt reduces the problem greatly, but my point was that it can be even further reduced to just the primes up to sqrt(n). If you check all the numbers, that's sqrt(n) values. But if you check the only the primes there's only (approx) sqrt(n)/ln(sqrt(n)) values.

But at the very least, you can skip every even number except 2, so you have approximately sqrt(2)/2 values. It halves your work.

Yea WHY not??? I only have 23 hours left.........and don't have nothing YET....

Guess you better get to work then. ;)

netsparc

11-03-2002, 02:07 PM

I wrote something like this at a summer camp at lockhaven university. It found the millionth prime in about 15 minutes.

Not that hard.

mingshun

11-03-2002, 02:12 PM

Originally posted by TacKat
Well you just do it in reverse. Every number not divisible by 2 up to 2^2 is prime; ie 3. Then every number not divisible by 2 or 3 up to 3^2=9 is prime; ie 5,7. Every number up to 7^2=49 not divisible by 2,3,5, or 7 is prime, etc etc.

Hmm, thanks :D
Obviously I couldn't catch what you mean earlier on.

C++ Im dead

11-03-2002, 02:13 PM

Originally posted by netsparc
I wrote something like this at a summer camp at lockhaven university. It found the millionth prime in about 15 minutes.

Not that hard.

Only 15 minutes???? DO you have 15 minutes right now??? Give it a try. :( please..

mingshun

11-03-2002, 02:16 PM

Originally posted by C++ Im dead
Only 15 minutes???? DO you have 15 minutes right now??? Give it a try. :( please..

netsparc meant the program takes 15 minutes to find out whether a million number is prime.

By the way, have you tried out the codes that we have posted here? You cannot depend on us 100% since we are not paid to do your assignments, you know?

C++ Im dead

11-03-2002, 02:24 PM

Originally posted by mingshun
netsparc meant the program takes 15 minutes to find out whether a million number is prime.

By the way, have you tried out the codes that we have posted here? You cannot depend on us 100% since we are not paid to do your assignments, you know?

yEA......im tying all the codes that where posted here.........but the more input the better.........:cool: ...........Im getting there......

ehawk

11-03-2002, 02:34 PM

Here is a code which successfully compiles and identifies perfect numbers (numbers whose factors add up to the given number) using a function. I think you should be able to alter it to find prime numbers, since to check for being a perfect number, you have to know the factors.

eats only heads

11-03-2002, 02:44 PM

damn it if you can't get anyware on your homework with out asking for help mabey you should be taking a less advanced class. Also cprogramming.com is a good site for c/c++ programming. Also try searching cplusplus.com there is some stuff there to.

C++ Im dead

11-03-2002, 03:31 PM

Originally posted by eats only heads
damn it if you can't get anyware on your homework with out asking for help mabey you should be taking a less advanced class. Also cprogramming.com is a good site for c/c++ programming. Also try searching cplusplus.com there is some stuff there to.

This is the first C++ programming class offer for beggfinners.....but the teacher has already jump into functions and array...........Function are suppose to be given in Intermidiate Programming not.....not for the first class.!!!!!

shadowrider

11-03-2002, 04:14 PM

i'm sure everybody has given their part of codes, so i'm sure by now, you should have your codes ready to demonstrate??:)
well, if for somewhat reason, you still don't understand or anything like that, you might want to check out the same thread you made under General discussion and i made a little simple example.
don't worry...we all struggled in the beginning but i find that the only way to get over it is to try to do everything by yourself. that way, you'll understand it and not forgetting about it.
so, with the helps given + the websites, you should get the idea (kind of.)
:D

good luck and feel free to post some basics idea of c++ if you still don't get.

ehawk

11-03-2002, 04:35 PM

okay...I found this code at free2code.net (I think). It tells you whether or not a number is prime. You should certainly be able to take this and ramp up through the numbers to find the primes.

You should just do a google search for "prime number c++ code". Lots of examples.

Anyway....

Program PrimeNumbers;
var k:integer;

Function Prime(n:integer):boolean;
var k,koren:integer;
Begin
Prime:=true;
koren:=round(sqrt(n));
for k:=2 to koren do
if (n mod k)=0 then Prime:=false;
End;

BEGiN
write('k=');Readln(k);
if k<>1 then
begin
if Prime(k) then writeln('This is a prime number.')
else Writeln('This number is not prime.');
end
else
writeln('You have entered 1');
readln;
ENd.

ehawk

11-03-2002, 04:39 PM

//**************************************
//
// Name: Prime Number Algorithm
// Description:Program uses the prime nu
// mber algorithm to do the obvoius (find p
// rime numbers)
// By: Tim Strazzere
//
//This code is copyrighted and has// limited warranties.Please see http://
// www.Planet-Source-Code.com/xq/ASP/txtCod
// eId.3986/lngWId.3/qx/vb/scripts/ShowCode
// .htm//for details.//**************************************
//

/* Prime Number Algorithm by Tim Strazzere */
#include <stdio.h>
#include <stdlib.h>
#define n 150 /* Constant for 'n' in the algorithm */
int main()

{
/* Initialization */
int P[150], i, j;
/* Zero out the matrix */
for(i=2; i<=n; ++i)
P[i] = 0;
/* Header */
printf("Prime Numbers Algorithm; Coded by Tim Strazzere\n");
printf("Here is a list of prime numbers from 1 to %i:\n\n\t\t\t\t\t",n);
/* Main Algorithm */
/* Nested for-loop to keep track of the number your checking */
for(i=2; i<n; ++i)

{
/* for-loop to check multiples with the current number */
for(j=2; i*j<n; ++j)
/* flag the multiples of the current numbers (can't be prime!) */
P[i*j] = 1;
/* if it's not a multiple then it must be prime! print it out */
if(P[i]!=1)
printf("%i\t",i);
}

/* Nice little format... */
printf("\n");
/* Press any key to continue... */
system("PAUSE");
return 0;
}

ehawk

11-03-2002, 04:43 PM

// To find the first 10 prime numbers
#include<iostream.h>
#include<conio.h>
void prime(int i, int c, int n, int j) /* This function can be used to find prime numbers to any extent ( first 10 here) by simply changing the while statement */
{
while (c <=10)
{
n=0;
i +=1;
for (j=1 ; j<=i ; j++ )
{
if ( i%j == 0)
{
n +=1;
}
}
if (n <=2 && n != 0)
{
cout<<i<<"\n";
c +=1;
}

}
}
void main()
{
int i=0,c=1,n,j;
prime(i,c,n,j);
cout<<"\n\nPress ENTER to close this Window";
getch();
}