GIDForums  

Go Back   GIDForums > Computer Programming Forums > C Programming Language
Reload this Page What's the algorithm to determine prime numbers?
User Name
Password
Register FAQ Members List Calendar Search Today's Posts Mark Forums Read

 
Page 1 of 2 1 2 >
 
Thread Tools Search this Thread Rate Thread
  #1  
Old 05-May-2008, 10:34
contherun contherun is offline
New Member
  
Join Date: Apr 2008
Posts: 18
contherun is on a distinguished road
Question

What's the algorithm to determine prime numbers?

Hi there,

COuld any one please give me the algorithm to determine weather a number is a "prime" or not?
  #2  
Old 05-May-2008, 11:42
L7Sqr L7Sqr is offline
Awaiting Email Confirmation
  
Join Date: Jul 2005
Location: constant limbo
Posts: 234
L7Sqr is a jewel in the roughL7Sqr is a jewel in the rough

Re: Whats the algorithem to determine prime numbers?

Quote:
Originally Posted by wikipedia
a prime number is a natural number greater than 1 which has exactly two distinct natural number divisors: 1 and itself
That should be pretty straightforward.
  #3  
Old 05-May-2008, 11:46
fakepoo fakepoo is offline
Regular Member
  
Join Date: Oct 2007
Posts: 969
fakepoo is a jewel in the roughfakepoo is a jewel in the roughfakepoo is a jewel in the rough

Re: Whats the algorithem to determine prime numbers?

A prime number is one that cannot be evenly divided by any number besides 1 and itself so:

CPP / C++ / C Code:
// return 1 if prime, otherwise 0
int IsPrime( int num )
{ int i;
  
  if(num == 0) return 0; // I guess, is zero prime?
  
  for(i=2;i<num/2+1;++i)
  { if(num%i == 0) return 0;
  }

  return 1;
}
  #4  
Old 05-May-2008, 12:13
davekw7x davekw7x is offline
Outstanding Member
  
Join Date: Feb 2004
Location: Left Coast, USA
Posts: 6,148
davekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to behold

Re: Whats the algorithem to determine prime numbers?

Quote:
Originally Posted by fakepoo
CPP / C++ / C Code:
// I guess, is zero prime?

Nowadays, the smallest prime integer is considered to be 2, although over the years some people have considered 1 to be a prime integer. (Zero has never been considered to be a prime integer under any definition that I have ever seen.)

From http://en.wikipedia.org/wiki/Prime_number

"In mathematics, a prime number (or a prime) is a natural number greater than 1 which has exactly two distinct natural number divisors: 1 and itself."

There's a little redundancy in that definition to emphasize that 1 is not a prime. (After all, if they just said, "a natural number that has exactly two distinct natural number divisors," wouldn't that be sufficient?)

Regards,

Dave
  #5  
Old 05-May-2008, 12:16
contherun contherun is offline
New Member
  
Join Date: Apr 2008
Posts: 18
contherun is on a distinguished road

Re: Whats the algorithem to determine prime numbers?

according to wiki zero is not a prime number:
http://en.wikipedia.org/wiki/Prime_Numbers
  #6  
Old 05-May-2008, 12:17
contherun contherun is offline
New Member
  
Join Date: Apr 2008
Posts: 18
contherun is on a distinguished road

Re: Whats the algorithem to determine prime numbers?

oops, i've reposted dave's, sorry
  #7  
Old 05-May-2008, 12:18
fakepoo fakepoo is offline
Regular Member
  
Join Date: Oct 2007
Posts: 969
fakepoo is a jewel in the roughfakepoo is a jewel in the roughfakepoo is a jewel in the rough

Re: Whats the algorithem to determine prime numbers?

Ok, thanks for the info. If we are in agreement that 1 is not prime, you'll have to adjust the function that I gave ever so slightly. Hope it helps you out.
  #8  
Old 05-May-2008, 12:19
contherun contherun is offline
New Member
  
Join Date: Apr 2008
Posts: 18
contherun is on a distinguished road

Re: Whats the algorithem to determine prime numbers?

Quote:
Originally Posted by fakepoo
A prime number is one that cannot be evenly divided by any number besides 1 and itself so:

CPP / C++ / C Code:
// return 1 if prime, otherwise 0
int IsPrime( int num )
{ int i;
  
  if(num == 0) return 0; // I guess, is zero prime?
  
  for(i=2;i<num/2+1;++i)
  { if(num%i == 0) return 0;
  }

  return 1;
}

In the for loop, please explain, why did you devide the num by two and then add a one to it?
  #9  
Old 05-May-2008, 12:41
fakepoo fakepoo is offline
Regular Member
  
Join Date: Oct 2007
Posts: 969
fakepoo is a jewel in the roughfakepoo is a jewel in the roughfakepoo is a jewel in the rough

Re: Whats the algorithem to determine prime numbers?

Quote:
Originally Posted by contherun
In the for loop, please explain, why did you devide the num by two and then add a one to it?
This is because you don't need to check all of the numbers, just the first half. Because none of the numbers that are greater than half of the number will divide evenly.
  #10  
Old 05-May-2008, 15:31
contherun contherun is offline
New Member
  
Join Date: Apr 2008
Posts: 18
contherun is on a distinguished road

Re: Whats the algorithem to determine prime numbers?

Thanks for all your answers
 
Page 1 of 2 1 2 >
 
« Previous Thread | Next Thread »

Recent GIDBlogGID Spam Detector 1.1.0 by gidnetwork

Thread Tools Search this Thread
Search this Thread:

Advanced Search
Rate This Thread
Rate This Thread:

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts
vB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Forum Jump

Similar Threads
Thread Thread Starter Forum Replies Last Post
prime numbers hiflya69 C++ Forum 5 19-Oct-2007 20:42
prime numbers help m3Gigah3rz C++ Forum 14 06-Sep-2006 14:00
Python script: Prime numbers crystalattice Python Forum 4 16-Apr-2006 08:19
Trouble with the logic of Prime numbers in a certain program. tylerfelix C++ Forum 1 02-Nov-2005 03:15
Prime Numbers from 0-300 Zorachus C++ Forum 15 12-Jul-2005 17:33

Network Sites: GIDNetwork · GIDApp · GIDSearch · Learning Journal by J de Silva, The

All times are GMT -6. The time now is 17:54.

Contact Us - GIDForums™ - Archive - Top

vBulletin, Copyright © 2000 - 2013, Jelsoft Enterprises Ltd.