Programmer's Corner Forum Index
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

Programmer's Corner - Forums


Classic - Prime Numbers

 
Post new topic   Reply to topic    Programmer's Corner Forum Index -> Code Wars
Author Message
Algorithms
Dragon


Joined: 21 Oct 2004
Posts: 343
Location: Florida
PostPosted: Wed Jul 20, 2005 2:45 pm    Post subject: Classic - Prime Numbers Reply with quote
Here is a classic, print off prime numbers from 0-100 or 0-n how ever high you feel like going.
Code:

# Python
n = 100
for i in range(n):
   prime = 1
   if i == 1 or i == 0:
      continue
   for j in range(n):
      if j == 0 or j == 1 or j == i:
         continue
      if i % j == 0:
         prime = 0
   if prime:
      print i

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
Back to top
Cerulean
Gokenin


Joined: 22 Oct 2004
Posts: 742
Location: London, England
PostPosted: Wed Jul 20, 2005 4:04 pm    Post subject: Reply with quote
*had forgotten this forum exists*
Back to top
WannaBe
Wiggles


Joined: 22 Oct 2004
Posts: 714
Location: CA
PostPosted: Wed Jul 20, 2005 4:17 pm    Post subject: Reply with quote
Code:
'Visual Basic 6
Dim i As Long, c As Long
Dim max_range As Long
Dim is_prime As Byte

max_range = 500

For i = 1 To max_range

    is_prime = 1
   
    For c = 2 To i - 1
        If (i Mod c) = 0 Then
            is_prime = 0
            Exit For
        End If
    Next c
   
    If is_prime = 1 Then Debug.Print i
   
Next i


Code:

<?php
//PHP
$max_range = 500;

for( $i=1;$i<=$max_range;$i++ )
{

   $is_prime = true;
   
   for( $c=2; $c<$i; $c++ )
   {
           if( $i % $c == 0 )
      {
                  $is_prime = false;
                  break;
           }
       }
   
   if( $is_prime ){ echo( $i . '<br />' ); }
}
?>


Code:
<html><!--java script-->
<head><title>Primes</title>
<script>
function echo_prime()
{
var max_range=500;
var i=0;
var c=0;
var is_prime=1;

for( i=1;i<=max_range;i++ )
{

   is_prime = 1;
   
   for( c=2; c<i; c++ )
   {
           if( i % c == 0 )
      {
                  is_prime = 0;
                  break;
           }
       }
   
   if( is_prime == 1 ){ window.document.getElementById("div_echo").innerHTML += i + "<br />"; }
}
}
</script>
</head>
<body onload="echo_prime();">
<div id="div_echo"></div>
</body>
</html>


edit:added java script
Back to top
aschenta
*narf*


Joined: 07 May 2003
Posts: 548
Location: Windsor Ontario Canada
PostPosted: Wed Jul 20, 2005 4:46 pm    Post subject: Reply with quote
C++
Code:

#include <iostream>

struct sNumber
{
   int iPrimeNumber;
   sNumber *pNext;
};

int _tmain(int argc, _TCHAR* argv[])
{
   sNumber *pStart = NULL;
   sNumber *pEnd = NULL;
   std::cout << "Please enter the number to stop at: ";
   int iMaxNumber = 0;
   std::cin >> iMaxNumber;
   pStart = new sNumber();
   pStart->iPrimeNumber = 2;
   pStart->pNext = NULL;
   pEnd = pStart;
   for (int i = 2; i < iMaxNumber; i++)
   {
      sNumber *pCur = pStart;
      bool bPrime = true;
      while (pCur)
      {
         if (i % pCur->iPrimeNumber == 0)
         {
            bPrime = false;
            break;
         }
         pCur = pCur->pNext;
      }
      if (bPrime)
      {
         sNumber *pNewItem = new sNumber();
         pNewItem->iPrimeNumber = i;
         pNewItem->pNext = NULL;
         pEnd->pNext = pNewItem;
         pEnd = pNewItem;
         std::cout << i << std::endl;
      }
   }
   // cleanup
   sNumber *pCur = pStart;
   while (pCur)
   {
      sNumber *pNext = pCur->pNext;
      delete pCur;
      pCur = pNext;
   }
   return 0;
}
Back to top
intrest86
Samurai++


Joined: 31 Dec 1969
Posts: 64
Location: Johns Hopkins
PostPosted: Wed Jul 20, 2005 5:45 pm    Post subject: Reply with quote
Code:
static void Main(string[] args)
{
   bool[] num = new bool[101];
   num[0] = num[1] = true;

   for (int i = 2; i<101; i++)
   {
      if (!num[i])
      {
         System.Console.WriteLine(i);
         for (int k = i+i; k<101; k+=i)
            num[k] = true;
      }
   }
}


I hope my incredibly short and efficient answer makes you cry Razz
Back to top
aschenta
*narf*


Joined: 07 May 2003
Posts: 548
Location: Windsor Ontario Canada
PostPosted: Wed Jul 20, 2005 7:09 pm    Post subject: Reply with quote
Quote:
I hope my incredibly short and efficient answer makes you cry

I don't get paid for short and efficient Razz and besides yours is .net so efficency gets thrown out the window Cool
Back to top
bdi
Nobody


Joined: 21 Oct 2004
Posts: 1646
Location: Chicago
PostPosted: Wed Jul 20, 2005 7:16 pm    Post subject: Reply with quote
intrest86 wrote:
Code:
static void Main(string[] args)
{
   bool[] num = new bool[101];
   num[0] = num[1] = true;

   for (int i = 2; i<101; i++)
   {
      if (!num[i])
      {
         System.Console.WriteLine(i);
         for (int k = i+i; k<101; k+=i)
            num[k] = true;
      }
   }
}


I hope my incredibly short and efficient answer makes you cry Razz

Gives me syntax errors in my VBScript interpreter. Confused
Back to top
intrest86
Samurai++


Joined: 31 Dec 1969
Posts: 64
Location: Johns Hopkins
PostPosted: Wed Jul 20, 2005 8:04 pm    Post subject: Reply with quote
bdi wrote:

Gives me syntax errors in my VBScript interpreter. Confused

Har har Mad

It's C#, and since it only has one memory allocation it is far from inefficient Razz. And not a single divide, so eat that Razz
Back to top
WbHack
Bushi


Joined: 27 Jan 2005
Posts: 335
Location: Seattle
PostPosted: Wed Jul 20, 2005 10:42 pm    Post subject: Reply with quote
Basic:
Code:
10 ? "2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 51 67 71 73 79 83 89 97"
20 End


(seriously though... this is a math thing... if someone doesn't do COBOL and/or FORTRAN, there's something wrong)
Back to top
WbHack
Bushi


Joined: 27 Jan 2005
Posts: 335
Location: Seattle
PostPosted: Wed Jul 20, 2005 10:45 pm    Post subject: Reply with quote
[quote="WannaBe"]
Code:
'Visual Basic 6

Code:
//PHP

Code:
<!--java script-->


c'mon, you can't do three in one post. that's not fair.
Back to top
Cerulean
Gokenin


Joined: 22 Oct 2004
Posts: 742
Location: London, England
PostPosted: Thu Jul 21, 2005 5:17 am    Post subject: Reply with quote
[quote="WbHack"]
WannaBe wrote:
Code:
'Visual Basic 6

Code:
//PHP

Code:
<!--java script-->


c'mon, you can't do three in one post. that's not fair.

Hear hear.. C++, Python, and java script were gone by the time I came to submit my entry Crying or Very sad
Back to top
aschenta
*narf*


Joined: 07 May 2003
Posts: 548
Location: Windsor Ontario Canada
PostPosted: Thu Jul 21, 2005 8:13 am    Post subject: Reply with quote
Quote:
Hear hear.. C++, Python, and java script were gone by the time I came to submit my entry

well apparently the rest of our submissions are long and inneficient so you're welcome to post something better...
Back to top
WbHack
Bushi


Joined: 27 Jan 2005
Posts: 335
Location: Seattle
PostPosted: Thu Jul 21, 2005 9:08 am    Post subject: Reply with quote
*narf* wrote:
well apparently the rest of our submissions are long and inneficient so you're welcome to post something better...

hm. the way i read it, just yours. Razz
Back to top
aschenta
*narf*


Joined: 07 May 2003
Posts: 548
Location: Windsor Ontario Canada
PostPosted: Thu Jul 21, 2005 11:38 am    Post subject: Reply with quote
*feels his banning finger start twitching*
Back to top
WannaBe
Wiggles


Joined: 22 Oct 2004
Posts: 714
Location: CA
PostPosted: Thu Jul 21, 2005 11:44 am    Post subject: Reply with quote
Shocked


man, sorry for posting three different langs, but I was bored. besides they are really all the same code. Razz

and btw *narf*'s code isn't inneficient, it is the only one that asks the user for the range. (thats not a suck up Wink)
Back to top
Ankou
Spam Mod


Joined: 22 Oct 2004
Posts: 1201
Location: Wisconsin
PostPosted: Thu Jul 21, 2005 3:09 pm    Post subject: Reply with quote
Okay just thought I'd toss in the Sieve of Eratosthenes method. I didn't feel like trying to do the Sieve of Atkin method right now, maybe a bit later.


With Comments:
Code:
<?php
// Highest value to check
$MAX = 100;
$HIGH_CHECK = floor(sqrt($MAX));
$REMAIN = array();
$PRIMES = array();

echo "Checking for primes b/n 1 and $MAX<br />Will only need to check to $HIGH_CHECK<br /><br />";

// Load the $REMAIN array
for($i = 2; $i <= $MAX; $i++){  array_push($REMAIN, $i); }

// Reverse array $REMAIN to be able to POP from array.
$REMAIN = array_reverse($REMAIN);

while(count($REMAIN) > 0){
  // Pop the value from array $REMAIN - this value is the
  // lowest remaining value in the list we need to check.
  $n = array_pop($REMAIN);

  // Since $n is the lowest value, it can be pushed onto
  // our list of prime numbers (array $PRIMES).
  array_push($PRIMES, $n);

  // If the lowest value of the $REMAIN array is greater than
  // the floor of the of the squareroot of our highest value,
  // then we can exit out of this process.
  if($n > $HIGH_CHECK) break;

  // If the values remaining ($REMAIN array) are divisible by
  // the lowest value of the $REMAIN array, which we popped
  // off before, they can be removed from the $REMAIN array.
  foreach($REMAIN as $key => $value){
    if($value % $n == 0){ unset($REMAIN[$key]); }
  }
}


// Merge and display array values
// Array $REMAIN is reversed so the numbers are in order.
foreach(array_merge($PRIMES, array_reverse($REMAIN)) as $show_val){
  echo $show_val . "<br />";
}

?>



Without comments:
Code:
<?php
$MAX = 100;
$HIGH_CHECK = floor(sqrt($MAX));
$REMAIN = array();
$PRIMES = array();

echo "Checking for primes b/n 1 and $MAX<br />Will only need to check to $HIGH_CHECK<br /><br />";

for($i = 2; $i <= $MAX; $i++){  array_push($REMAIN, $i); }
$REMAIN = array_reverse($REMAIN);

while(count($REMAIN) > 0){
  $n = array_pop($REMAIN);
  array_push($PRIMES, $n);
  if($n > $HIGH_CHECK) break;

  foreach($REMAIN as $key => $value){
    if($value % $n == 0){ unset($REMAIN[$key]); }
  }
}

foreach(array_merge($PRIMES, array_reverse($REMAIN)) as $show_val){
  echo $show_val . "<br />";
}

?>
Back to top
bdi
Nobody


Joined: 21 Oct 2004
Posts: 1646
Location: Chicago
PostPosted: Thu Jul 21, 2005 3:51 pm    Post subject: Reply with quote
WannaBe wrote:
Shocked


man, sorry for posting three different langs, but I was bored. besides they are really all the same code. Razz

and btw *narf*'s code isn't inneficient, it is the only one that asks the user for the range. (thats not a suck up Wink)

I thought unnecessary complexity was admired in these circles? Then again, so is efficiency. Double edged sword. Razz

Actually, it would make a good source code sample for a linked list.
Back to top
aschenta
*narf*


Joined: 07 May 2003
Posts: 548
Location: Windsor Ontario Canada
PostPosted: Thu Jul 21, 2005 4:17 pm    Post subject: Reply with quote
Quote:
Actually, it would make a good source code sample for a linked list.

I don't get what you're trying to say Confused
Back to top
bdi
Nobody


Joined: 21 Oct 2004
Posts: 1646
Location: Chicago
PostPosted: Thu Jul 21, 2005 4:22 pm    Post subject: Reply with quote
*narf* wrote:
Quote:
Actually, it would make a good source code sample for a linked list.

I don't get what you're trying to say Confused

That you're a di..*narf*

Can't say that here. Razz
Back to top
WbHack
Bushi


Joined: 27 Jan 2005
Posts: 335
Location: Seattle
PostPosted: Thu Jul 21, 2005 9:50 pm    Post subject: Reply with quote
ok... Now that all the normal languages are used up *ahem wannabe* .... Rube Goldberg it....... how cumbersome can you make it (that's at least semi-relevant) so that it still does the same thing?
Back to top
Display posts from previous:   
Post new topic   Reply to topic    Programmer's Corner Forum Index -> Code Wars All times are GMT - 5 Hours
Page 1 of 1

 


Powered by phpBB © 2001, 2002 phpBB Group