New Way to Implement Sieve of Eratosthenes !!

[CMinus]

All the Implementation I saw had used Vector Library Which I don't know how to use !! So I made A little Code without using Vectors !!
Tell me ur Opinions
Note : I used a Const just for my self I will adjust it later using pointers for User interaction

Thanks ne555 , Here it's After Loop!!

#include<iostream>
using namespace std;

int main()
{ 
const int n = 150;
int num [n];
bool prime [n];
fill_n(prime,n,true);
prime[0]=false;
int x;
int k;
int firstprime=2;
    
for (x=0;x<=n-1;x++)
	{num[x]=x+1;
	}

while(firstprime<n-1)
{
     for(int K=2*firstprime; K<=n; K+=firstprime)
		      prime[K-1] = false;
	 
	 for (x=0;x<=n;x++)
	 {
		 if(prime[x]==true && num[x] > firstprime)
		 {
			 firstprime=num[x];
			 break;
		 }
	 }
}

	  for(x=0;x<n;x++)
	 {
		if(prime[x]==true)
	    cout<<num[x]<<endl;
	 }
   
	  system("PAUSE"); 
return 0;
}

[ne555]

The num array is useless, you could just do x+1.

I think that loop 19-24 is obfuscated.

for(int K=2*last_prime; K<=n; K+=last_prime)
  prime[K-1] = false;

for (x=0;x<=n;x++) You could start from the last_prime instead of 0. Also you are accessing out of bounds.
That jump makes the code harder to follow, replace it with a loop.

if( (((prime[x]==true)==true)==true)==(true==true) )

[CMinus]

The loop 19-24 Makes the multiplies of primes false !!
And About the loop 36-40 It Shows the Prime Numbers !!
And I don't understand ur last line !!

[ne555]

1_ Yes, I know. But the condition was unnecessarily complicated.

2_ Sorry, I'm referring to the loop 24-31, where you search for the next prime.

3_ prime[x] is a Boolean, so it can only have true or false. You should ask its value directly
if( prime[x] )

[CMinus]

It' Not Complicated as you Think Because if I didn't write the second condition the Prime will be always 2 !!
& It doesn't work with really big numbers ( Gives Me Stack Overflow Error )!!! Damn it I wanna optimize this but I have Physics Lecture I have to study for :@:@

[ne555]

while(times < n/firstprime) That is what I think is obfuscated (I don't remember it exactly)

	 for (x=0;x<=n;x++) // x=n is out of bounds
	 {
		 if(prime[x] && num[x] > firstprime)
		 {
			 firstprime=num[x];
			 break;
		 }
	 }

[JLBorges]

#include <iostream>

int main()
{
    const int N = 150 ;
    bool sieve[N] ;
    for( int i=0 ; i<N ; ++i ) sieve[i] = true ;
    // as pointed out earlier, we don't need a seperate array int num [n]
    // to hold the prime numbers. We will organize the sieve such that
    // if sieve[i] == true at the end, i is the prime number

    // start the loop with i == 2. we know that 0 and 1 are not prime numbers
    // we will just ignore the first two values
    // this gets rid of the obfuscation that was mentioned earlier
    for( int i=2 ; i<N ; ++i ) if( sieve[i] ) 
    {
        // we need to check the sieve only from i*i onwards (why?)
        // to get the next multiple of i, we add i to the current multiple
        for( int j = i*i ; j<N ; j += i ) sieve[j] = false ;
    }

    for( int i=2 ; i<N ; ++i ) if( sieve[i] ) std::cout << i << ' ' ;
    std::cout << '\n' ;
}

[CMinus]

Well JLBorges Ur Code is more efficient than mine ( Mine was crap ) ! But One Thing U missed in ur code IF N was an Prime Number It won't Show it

So
I will Edit the last loop condition

for( int i=2 ; i<N+1 ; ++i ) if( sieve[i] ) std::cout << i << ' ' ;
    std::cout << '\n' ;

Also This One to Make The last Number False
for( int j = i*i ; j<N+1 ; j += i ) sieve[j] = false ;

But It still Doesn't work With Big Numbers Stack Overflow Error I think I will learn vectors I read it's Less Memory Consuming
Well Guys I think I will give up Playing With Primes Because it drives me crazy (O_o)

[JLBorges]

> I will Edit the last loop condition ....
> for( int i=2 ; i<N+1 ; ++i ) if( sieve[i] ) std::cout << i.... << ' ' ;

> Also This One to Make The last Number False
> for( int j = i*i ; j<N+1 ; j += i ) sieve[j] = false ;

The array has just N elements. bool sieve[N] ;
The last element of the array can be accessed with sieve[N-1]
With sieve[N] , you will be trying to access an element that does not exist.


> But It still Doesn't work With Big Numbers Stack Overflow Error

The amount of memory available on the run-time stack is limited ( typically to a very small portion of the total memory that is available to the program).

Changing the storage duration of the array with static bool sieve[N] ; would typically allow the array to be of a larger size than at present.


> I think I will learn vectors I read it's Less Memory Consuming

Learning to use a std::vector<> is a very good idea.

However, It would consume at least as much memory (and a bit more) as a C-style array. But the memory it uses is dynamically allocated; it would use just a few bytes on the stack.

[CMinus]

I totally agree with u but about arrays if u run ur code & Initialized n = 997 or any prime
It won't Show up in the result :)
Oh I forget that Sieve Theory Find the Primes before a specific number , it doesn't do anything with the limit !

[JLBorges]

> Initialized n = 997 or any prime It won't Show up in the result :)
> Find the Primes before a specific number , it doesn't do anything with the limit !

Right. So if what is needed is all primes up to and including N, make the size of the sieve equal to N+1

#include <iostream>

int main()
{
    const int N = 997 ; // prime numbers upto and including N
    const int SZ = N + 1 ; // size of sieve

    bool sieve[SZ] ;
    for( int i=0 ; i<SZ ; ++i ) sieve[i] = true ;

    for( int i=2 ; i<SZ ; ++i ) if( sieve[i] )
        for( int j = i*i ; j<SZ ; j += i ) sieve[j] = false ;

    for( int i=2 ; i<SZ ; ++i ) if( sieve[i] ) std::cout << i << ' ' ;
    std::cout << '\n' ;
}

[CMinus]

I think Both of them will work :) Have a good day !!