prime numbers

[narvey ann]

create a program to print all prime numbers between 1 to 100.

[ddanbe]

Are WE supposed to do that?
it is YOUR assignment, and we will gladly be helping with the code you already have and having problems with.
It all starts with knowing what a prime number is. You know that, don't you?

[Prashant_3]

include <stdio.h>

include <conio.h>

void main()

{

int a[100],i,j=2;
clrscr();
for(i=0;i<100;i++)
a[i]=i+1;
printf("Prime Number between 1 to 100 \n");
for(i=0;i<100;i++)

{


for(j=2;a[i]>j;j++)
  {
 if(a[i]%j==0)
 break;
  }
 if(a[i]==j || a[i]==1)
   printf("%d\t",a[i]);
}

getch();

}

[android9000]

sieves are much faster because they skip a bunch of numbers. There are three really well known ones linked to from the erastothenes wiki page. They are Atkins (fastest), Sundaram (next best), Erastothenes.

http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
http://en.wikipedia.org/wiki/Sieve_of_Sundaram
http://en.wikipedia.org/wiki/Sieve_of_Atkin

class Erastothenes{
 //TODO sieve of erastothenes for numbers <= 1,000,000

private:
 //initialize array of 1,000,000 potential numbers at 0
 static int nums[1000000];

 //max: our nth prime
 int max;

 //the starting point (first is 2 since 1 is prime and everything divisible by 1)
 int p;

 void perfsift(){

  int i=0;

  //iterate through the numbers up to our potential maximum
  while(i<(max*100) & (p*i)<(max*100))
  {
   nums[(p*i)]=(p*i);
   i++;
  }

  i=0;

  //get the next starting p value if in existance
  while(i<(max*100) & nums[i] != 0)
  {
   i++;
  }

  //recurse the function if there is an unmarked number greater than the current p
  if(nums[i]==0)
  {
   p=i;
   perfsift();
  }

 }


public:
 //empty constructor
 Erastothenes(){
  max=0;
  p=2;
 }

 Erastothenes(int inmax){
  max=inmax;
  p=2;
 }

 //sift through the array
 int sift(){
  if(max>0)
  {
   //sift at max*100
   perfsift();

   //get the remaining numbers, which are prime, up to the nth prime
   int j=0;
   int i=0;

   while(j<max & i<sizeof(nums)){
    if(nums[j]==0)
    {
     j++;
    }
    i++;
   }

   if(j<max){
    printf("No Prime Found. The prime must be less than %i",sizeof(nums));
   }
   else{
    return i;
   }

  }
  return -1;
 }

};

[Moschops]

#include <iostream>

int main()
{
  std::cout << "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" << std::endl;
}

[AndrisP]

#include <iostream>
using namespace std;

bool IsPrime(int number)
{
    for (int i=2; i<=number/2; i++)
    {
        if (number % i == 0) return false;
    }
    return true;
}


int main()
{
    for(int i=2; i<=100; i++)
    {
    cout << i << (IsPrime(i)?" is prime":"") << "\n";
    }
system ("PAUSE");
return 0;
}

[iamthwee]

#include <stdio.h>
  #include <cstring>

  char _[10000000],____[100000000], _____[10000000],__[10000000], *___;

  #define      ________OOOOOOO________      ___,2+(((((((((((_
  #define      _____OOO_______OOO_____      2+(__
  #define      ___OO_____________OO___      "__"
  #define      __O____O_______O____O__      ___=_____,"")
  #define      _O____OOO_____OOO____O_      ___,_+(_
  #define      O_____OOO_____OOO_____O      ____,___)))for(;____
  #define      O______O_______O______O      ___,____)?___+=(__
  #define      O_____________________O      __,_))))?"%d\n":""
  #define      O____O___________O____O      __,"__")),_)):(___
  #define      _O____OO_______OO____O_      _,"_"));fprintf(stderr
  #define      __O_____OOOOOOO_____O__      ____,"_");for(;____
  #define      ___OO______________O___      ____,___);___
  #define      _____OOO________OO_____      __
  #define      ________OOOOOOOO_______      ____,"__")

  int main() {
      strcpy(__O_____OOOOOOO_____O__, strcat(________OOOOOOOO_______,
      strcpy(__O____O_______O____O__, strcpy(_____OOO________OO_____,
      strcpy(_O____OO_______OO____O_, strstr(___OO_____________OO___,
      strcpy(_O____OOO_____OOO____O_, strspn(O_____________________O,
      strspn(O_____OOO_____OOO_____O, strcmp(___OO______________O___,
      strstr(O______O_______O______O, strspn(_____OOO_______OOO_____,
      strcat(O____O___________O____O, strcat(________OOOOOOO________,
      strcat(_,"__")))))))))))))));
  }

Do I win? I also put a bug in it?

[AndrisP]

Yes, iamthwee. Congratulations!

[android9000]

Please do your own assignment

[ddanbe]

@AndrisP: calculate: SQ = sqrt(number); (also include math.h of course)
On line 6 of your code change number/2 with SQ

[Slavi]

#include<iostream>
using namespace std;

void primes(int n){
  bool isPrime[n+1];
  for(int i=2; i<=n; i++)
    isPrime[i]=true;
  //
  for(int i=2; i<=n; i++){
    if(isPrime[i]){
      cout << i << " ";
      for(int j=2*i; j<=n; j+=i) isPrime[j]=false;
    }
  }
  cout << endl;
}


int main (){
  primes(100);
}

Congratulations your homework was done .. :D
iamthwee nice one :D

[Banfa]

It should be noted that for finding primes between in the range 1 - 100 any of the sieves are overkill of a high order.

since 1 is prime

Actually most university level matamaticians no longer think of 1 as prime, it is just a (very) special case. As far as I can tell this is because they had too many theorys/laws that went "for all primes, except 1, X is true" so they changed their minds about 1 being prime.

for (int i=2; i<=number/2; i++)

Very un-optimised, to start with if you test 2 independantly initially then you can skip testing all the other prime numbers (including ddanbe's suggested optimisation)

if ((number % 2) == 0) return false;
int sq = sqrt(number)
for (int i=3; i<=sq; i++)

You can take this further and apply a similar optimisation for multiples of 3 noting that every 3rd odd number is a multiple of 3

if ((number % 2) == 0) return false;
if ((number % 3) == 0) return false;
int sq = sqrt(number)
int step = 4;
for (int i=5; i<=sq; i+=step)
{
    step = 6 - step;
}

ddanbe optimisation reduces the number of check steps by a factor of 2 / sqrt(n) my optimisation further reduces it by approximately a factor of 1/3 resulting in checking each number for primeality against approximately 2 / 3.sqrt(n) less other values. If you were looking for primes in the range 1 - 1000 then you end up performing about 2% of the checks you would have to perform with a straight loop

for (int i=2; i<=number/2; i++)

[rubberman]

Ah, prime numbers! One of my favorite subjects when I was studying public key encryption algorithms back in 1984-1985. I wrote some interesting prime factorization algorithms that were quite efficient so I could generate Goedel numbers from random strings, and extract the strings from the numbers in turn. Over the years, other stuff caught my interest, such as efficient algorithms to distribute computational loads over large networks of dis-similar systems. I'm working a lot in big data analytics today... :-)