prime numbers help

m3Gigah3rz · #1 27-Aug-2006, 06:07

Hi im having problem with prime numbers i need to find all the prime numbers from 1 -100 and this is what i code a very simple code

CPP / C++ / C Code:

#include <iostream>
#include <conio.h>
using namespace std;
int main()
{

for(int x = 2; x <=100; x++){
for(int y = 2; y < x; y++){
if(x%y!=0){
           cout << x << "\n";
          
}
}
}
getch();
}

im such a noob...

WaltP · #2 27-Aug-2006, 06:28

Quote:

Originally Posted by m3Gigah3rz

Hi im having problem with prime numbers i need to find all the prime numbers from 1 -100 and this is what i code a very simple code

Code:

#include <iostream>
#include <conio.h>
using namespace std;
int main()
{

for(int x = 2; x <=100; x++){
for(int y = 2; y < x; y++){
if(x%y!=0){
           cout << x << "\n";
          
}
}
}
getch();
}

im such a noob...

You'd have better luck by setting a flag to TRUE outside the 2nd loop and if the if statement returns ==0 set the value to FALSE. The when you exit the loop, if the value is still TRUE you have a prime number.

Please read that obnoxious "Read This First" post to see how to properly post code and ask good questions that are answerable.

Also, search these forums to see other discussions about prime numbers. It'll save you a lot of time -- you won't have to wait for an answer. Primes have been asked about many times.

As a noob, you should learn how to format your code now before you get into bad habits. See this for some ideas.

And getch() not a good choice to pause the program. In C++, cin is better. It's part of the language. getch() is not a Standard C++ function.

m3Gigah3rz · #3 27-Aug-2006, 08:32

tnx for the help i completed it^^.... and also can you check my code if i have done something wrong....tnx here's the code

Code:

#include <iostream>

using namespace std;
int main()
{

for(int x = 2; x <=100; x++){
for(int y = 2; y < x; y++){
bool prime = true;
if((x%y)==0){
           prime = false;
           break;
           }
if(prime){
            cout << x << "\n";
            break;
            }
}
}
cin.get();
}

and btw is there any other way doing this without using flags??

__________________________________________________ ___________________________________

ooooopsss i think i know how to do the other way......is my coding right??? cause it's running good.... here's the code

Code:

#include <iostream>

using namespace std;
int main()
{
int av;
for(int x = 2; x <=100; x++){
for(int y = 2; y < x; y++){
av = x%y;
if(av==0){
           break;
           }
else{
            cout << x << "\n";
            break;
            }
}
}
cin.get();
}

tnx.....if you know any other way teach me how to do it.....^^ i will be very happy...

davekw7x · #4 27-Aug-2006, 14:57

Quote:

Originally Posted by m3Gigah3rz

tnx for the help i completed it
.
.
.
and btw is there any other way doing this without using flags??
.
.
.
cause it's running good.
.
.

Both of your examples print out all of the 49 odd numbers from 3 to 99.

Actually there are 25 prime numbers less than 100, and here they are:

Code:

 2  3  5  7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

So, I don't think you have quite finished.

Here's my take on the problem statement, expressed in a "top-down" computer-like language. Why do I say "computer-like"? Because I am already thinking of loops. Why do I say "top-down"? Because this is a big picture of the goal, without any particular attention to little details.

Code:

Make a loop that lets x go from 2 to 100:
    If x is prime, print its value

That's easy enough to say, but how do we do the "good stuff"?
(Determine whether a given number is prime.)

Let's just look at this part:

For a given number, x, (where x is greater than or equal to 2 and less than 100) how can we determine whether x is a prime number?

Here's a "brute force" way:

Code:

Make a loop that starts with y = 2 and quits when y reaches x
begin loop
    If (x % y == 0) then
      we know it isn't a prime number; break out of the loop;
    else
      increment y
    end if
end of loop

After the loop, if the value of y is less than x, we know
that it left the loop early. That is, we found a divisor of
x, so x can't be a prime number.

On the other hand:

After the loop, if we see that y is equal to x, then we know
that we went through the entire loop and didn't find any
divisor, so it is a prime number.

In something that is more like a C program:

CPP / C++ / C Code:

    for (x = 2; x < 100; x++) {
        for (y = 2; y < x; y++) {
           /* if y is a divisor of x, break out of the loop */
           
        }
        /* do the test here to see whether this x is a prime number 
         * and print the value of x if it is
         */
    }

Note to more experienced programmers:

Now, let's not get embroiled in some discussion about how this is not a very efficient method for finding prime numbers; I know that just as well as you. My point was to attempt to use the starting position of the person requesting help, and show one way of approaching the problem.

If any one has other elementary ways of telling a beginning programmer how to do this, I welcome any and all contributions (and I'll bet other beginners will, too).

Regards,

Dave

"Implement first; optimize later."
---davekw7x

tufan · #5 28-Aug-2006, 13:11

the better and more efficient way is:

CPP / C++ / C Code:

#include <iostream>
using namespace std;
int main()
   {
   int c;       
   for(int i=2;i<100;i++)
      {
      c=0;
      for(int j=i/2;j>0;j--)
         {
         if(i%j==0)
            c++;
         }
      if(c==1)
         cout<<i<<"\t";
      }
   return 0;
   }

MichaelS-R · #6 28-Aug-2006, 15:22

Quote:

Originally Posted by davekw7x

Actually there are 25 prime numbers less than 100, and here they are:
Code:

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

So, I don't think you have quite finished.

Actually, there are 26 - you missed out 1 (definition of a prime number: "a number only divisible by 1 and itself")

LuciWiz · #7 28-Aug-2006, 15:24

Quote:

Originally Posted by MichaelS-R

Actually, there are 26 - you missed out 1 (definition of a prime number: "a number only divisible by 1 and itself")

That is the definition, but 1 is the exception!

Every rule has an exception. <- even this one

Best regards,
Lucian

davekw7x · #8 28-Aug-2006, 15:28

Quote:

Originally Posted by MichaelS-R

d
Actually, there are 26 - you missed out 1 (definition of a prime number: "a number only divisible by 1 and itself")

Actually the definition goes more like this:

Quote:

Originally Posted by http://mathforum.org/dr.math/faq/faq.prime.num.html

A prime number is a positive integer that has exactly two positive integer factors, 1 and itself

Want more?

Quote:

Originally Posted by http://en.wikipedia.org/wiki/Prime_number

In mathematics, a prime number (or a prime) is a natural number that has exactly two (distinct) natural number divisors, which are 1 and the prime number itself. There exists an infinitude of prime numbers, as demonstrated by Euclid in about 300 B.C.. The first 30 prime numbers are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, and 113 (sequence A000040 in OEIS); see the list of prime numbers for a longer list.

One justification for not allowing 1 to be considered a prime number in the definition:

Quote:

Originally Posted by http://mathworld.wolfram.com/PrimeNumber.html

The number 1 is a special case which is considered neither prime nor composite (Wells 1986, p. 31). Although the number 1 used to be considered a prime (Goldbach 1742; Lehmer 1909; Lehmer 1914; Hardy and Wright 1979, p. 11; Gardner 1984, pp. 86-87; Sloane and Plouffe 1995, p. 33; Hardy 1999, p. 46), it requires special treatment in so many definitions and applications involving primes greater than or equal to 2 that it is usually placed into a class of its own. A good reason not to call 1 a prime number is that if 1 were prime, then the statement of the fundamental theorem of arithmetic would have to be modified since "in exactly one way" would be false because any n==n.1. In other words, unique factorization into a product of primes would fail if the primes included 1. A slightly less illuminating but mathematically correct reason is noted by Tietze (1965, p. 2), who states "Why is the number 1 made an exception? This is a problem that schoolboys often argue about, but since it is a question of definition, it is not arguable." As more simply noted by Derbyshire (2004, p. 33), "2 pays its way [as a prime] on balance; 1 doesn't."

Etc., etc. (and etc.).

Regards,

Dave

davekw7x · #9 28-Aug-2006, 15:30

Quote:

Originally Posted by LuciWiz

That is the definition, but 1 is the exception!

Every rule has an exception. <- even this one

Best regards,
Lucian

Not allowing 1 to be considered a prime number:
It's not a rule; it is a definition, accepted with good reason by modern mathemeticians. A definition is inarguable.

Regards,

Dave

MichaelS-R · #10 28-Aug-2006, 15:32

Quote:

Originally Posted by LuciWiz

That is the definition, but 1 is the exception!

Every rule has an exception. <- even this one

Best regards,
Lucian

I stand corrected. Interestingly though (this is not something that I have dealt with in a long time), when I was at university it was regarded as a prime number. With computers having progressed to the point they have I can see why it would be confusing to consider it as such still (I always though it was a bit of an anomally).

Thread Tools	Search this Thread
Show Printable Version Email this Page	Search this Thread: Advanced Search
Rate This Thread
Rate This Thread:

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Python script: Prime numbers	crystalattice	Python Forum	4	16-Apr-2006 09:19
subscript error in coding	warborules	C Programming Language	6	27-Nov-2005 18:16
Linear Search	eccoflame	C Programming Language	3	19-Apr-2005 09:36
prime numbers	quasimof	C++ Forum	1	01-Nov-2004 20:35
Help w/ prime # determination	crystalattice	C Programming Language	17	18-Apr-2004 22:43

prime numbers help

Re: prime numbers help

Re: prime numbers help

Re: prime numbers help

Re: prime numbers help

Re: prime numbers help

Re: prime numbers help

Re: prime numbers help

Re: prime numbers help

Re: prime numbers help