Thread: Basic Array help

this is more of a math question you have me thinks, the computational methods involved in finding primes

faster way to do it, but before you call isprime (i) you have to call isprime (i) for all primes below i. my recursion also isnt self-starting but i think it could be easily

Code:

// wheee, i wrote this

#include <stdio.h>
#include <stdlib.h>

#define PUT(x) myarray[(x-1)>>3] = myarray[(x-1)>>3] | (1 << ((x-1) % 8))
#define GET(x) myarray[(x-1)>>3] & (1 << ((x-1) % 8))

#define MAXNUMBER 50 // prints all primes from 1 to MAXNUMBER

unsigned char myarray[(MAXNUMBER>>3)+1] = {0};

#ifndef SLOWMETHOD

int isprime (int i)
{
  int j;
  for (j = 2; j < i; j++)
    if (GET (j)) // j is prime
      if ((i % j) == 0) // i is evenly divisible by j
        return 0; // i is not prime
  return 69; // i is prime
}

// this does the same thing but is slower
// also you dont have to call isprime (x) for all primes
// smaller than x first
#else // ifndef SLOWMETHOD

int isprime (int i)
{
  int j;
  for (j = 2; j < i; j++)
    if ((i % j) == 0) // i is evenly divisible by j
      return 0; // i is not prime
  return 69; // i is prime
}

#endif // ifndef SLOWMETHOD

int main (void)
{

  int i;               
  printf ("Computing all primes from 1 to %i...\n", MAXNUMBER);
  PUT (2);
  PUT (3);
  PUT (5);  

  for (i = 6; i <= MAXNUMBER; i++)     
    if (isprime (i))
      PUT (i);

  printf ("Dun!  All primes from 1 to %i:\n", MAXNUMBER);
  for (i = 1; i <= MAXNUMBER; i++)
    if (GET (i))
      printf ("%i\n", i);

  printf ("--END--\n");

  return EXIT_SUCCESS;
}

This is more of an algorithmic problem than anything else. Prime numbers are divisible by themselves and 1, nothing else. The brute force method is to loop through every number from N - 1 to 2 and check if N % current is 0. If it is then the number is not prime. What you need to do is find an algorithm for finding a prime (hint: www.google.com) and then write a function which checks each value from N - 1 to 2:

Code:

int i = 0;
int primeArray[200] = {0};

for ( current = N - 1; current > 1; current-- )
  primeArray[i++] = isPrime ( current );

Then just print out the array. There are more efficient methods, but the oracle that is google can tell you about them, saving my poor little fingers the stress of detailing everything.

-Prelude

my code example has one main difference than the dog's and preludes: it takes advantage of the fact that you only have to test for divisiblity by all _prime_ numbers smaller than a number, not all numbers (unless you compile with -DSLOWMETHOD). this is not useful if you just want to find if a random number is prime, but if you have already found if all the numbers smaller than your test number are prime (for example if you're making a list of them), then it is faster.

there are also advanced algorithms used with very large numbers that are beyond our scope.

this is easier to understand, but wastes memory:

Code:

// wheee, i wrote this

#include <stdio.h>
#include <stdlib.h>

#define PUT(x) myarray[(x-1)] = 1
#define GET(x) myarray[(x-1)]

#define MAXNUMBER 50 // prints all primes from 1 to MAXNUMBER

unsigned char myarray[MAXNUMBER] = {0};

/* beyond this point use original code */

Originally posted by datainjector
Moi u seem to confuse people man... Look at ur code .Do u think that a guy who has been programming for 2 months and just started arrays will understand that??Take it easy yoo it aint a contest ..

the bit packing thing was copied from other code i had on hand. maybe it is too confusing. however the modified code which i posted below it is pretty simple imo.

Or just find a list of all of the primes between 1 and 200, and stick them in the array when you initialize it:

int array[] = { 1, 2, 3, 5, 7, 11, 13, 17... };

But I doubt that's what your teacher wants.

Quzah.

Originally posted by quzah
Or just find a list of all of the primes between 1 and 200, and stick them in the array when you initialize it:

int array[] = { 1, 2, 3, 5, 7, 11, 13, 17... };

But I doubt that's what your teacher wants.

Quzah.

BUHAHAHAAA