1. Just wondering, is there anywhere we can join in on the competition, or is it closed?

2. It's closed. Sorry.

I have no clue what sieves are, so sorry about that too. =\

Code:
```//////////
//Kevin Yin
//July 12, 2007
//Lists of primes

//Speedups possible:
//
//maybe instead of "= 0", "^= itself"
// -	cprogramming.com forums say "= 0"  is faster
//
//hardcoding in imn and smn
//
//maybe having a miraculous way of using mods to speed up the array
// -	looked up Sieve of Atkin, not possible

using namespace std;

#include <iostream>

int main()
{
int limit; //highest value
int increm; //value checked
int small; //increm checking increm
int square = 0; //square root of limit
bool cor = true; //whether to output
bool *array = NULL; //for speeding things up
int acrem; //for the array
int alim; //for the array, upper bound
int smn = 2, imn = 4; //how much to increm them by
//imn is reversed, so keep it like this

cout << "This program outputs prime numbers up to a number.\n";
cout << "Please insert that number.\n";
cin >> limit;

if (limit <= 1)
{
cout << "Don't be stupid.\n";
return 0;
}

alim = limit / 2 + 1;

array = new bool[alim];

for (acrem = 0; acrem < alim; acrem++)
array[acrem] = true;

//yes, what a cheater I am =)
cout << "2\n3";

for (increm = 5; increm <= limit; increm += imn) //incrementing the div by 2, from 7
{
//changes imn
imn = 2 + (imn == 2) * 2;

if (array[increm / 2]) //seeing if the array spot for the div is 0
{
//making a square root
while (square * square <= increm)
square++;

//the actual doing
for (small = 5; small <= square; small += smn) //incrementing small from 5, by 2
{
if (array[small / 2]) //if small is divisible
if (!(increm &#37; small)) //seeing if increm is divisible by small
{
//sets cor to 0
cor = false;

if (array[small * 3 / 2])
for (acrem = small * 3 / 2; acrem <= alim; acrem += small)
array[acrem] = false;
break;
}
smn = 2 + (smn == 2) * 2;
}

smn = 2;

//displaying and updating
if (cor)
{
cout << '\n' << increm;

for (acrem = increm * 3 / 2; acrem <= alim; acrem += increm)
array[acrem] = false;
}
cor = true;
}
}
cout << '\n';
}```
The principle of smn and imn are that

0 _ 2 3 4 _ 6 _ 8 9 10 _ 12 _

(see a pattern?) They add 2, then 4, then 2...

The small divisor starts at 5 because the large divisor automatically skips numbers divisible by 2 and 3.

The array only stores odd numbers.

It's currently working with a max because I don't know what I should set the max at for 20 seconds so far.

Lastly, if you feel that you don't want to scroll through the code, I can just add it to cpp.sf.net and put a link here.

3. I have no clue what sieves are, so sorry about that too. =\
That is the point Salem made earlier: before you do micro-optimisations (and if possible, before you even start coding), do the major optimisation by using a fast algorithm.

The hybrid approach I suggested has a problem: it "wastes" time by generating a list of primes, so it only wins out when the range becomes sufficiently large. As such, for a PHP based contest that I entered a couple of years back, it had pretty bad performance as the time limit for the primality testing was 3 seconds. However, I digged up some old C++ code in which I had implemented that algorithm and tested against your code, and even as soon as the millionth prime range my program was noticeably faster than yours.

Incidentally, the C++ keywords for true and false are entirely lowercase, and you need to qualify the names from the std namespace.

4. Wait, so it's standard to use lowercase words?

I don't know what's going on, but GCC doesn't seem to need the std namespace. I got used to it (coding in Windows) a project member took it out, and my code still worked fine.

Mine wastes time generating a list, but instead of listing primes, it has an array in which each member corresponds to one odd number. So in the end, you still have to check the array, and check every single box (1 or 0) until you either hit a valid divisor or until you hit the square root of the number.

I was dead wrong that sqrt() was faster than my while loop. The while loop makes the code run 40&#37; faster.

5. Wait, so it's standard to use lowercase words?
Yes, in C++.

I don't know what's going on, but GCC doesn't seem to need the std namespace. I got used to it (coding in Windows) a project member took it out, and my code still worked fine.
Rather unusual. I tested with the MinGW port of g++ 3.4.2

6. Same here: the MinGW I have needs the std namespace. I started with the package that came with Dev-C++, then overwrote it with the MinGW from the CVS.

For some reason, my MinGW doesn't let me declare variables anywhere inside loops (initialization fields are banned too), and doesn't let me declare file I/O pointers anywhere but in the top level inside of functions. So it really stinks, and I'm really not sure what kind of compiler it is now.

But my GCC works fine.

Is null also supposed to be lowercase?

I guess I used a faster version of the Sieve of Eratosthenes.

8. Is null also supposed to be lowercase?
No, uppercase, though you can also use 0.

9. NULL is a define, not a keyword.

10. For some reason, my MinGW doesn't let me declare variables anywhere inside loops (initialization fields are banned too), and doesn't let me declare file I/O pointers anywhere but in the top level inside of functions. So it really stinks, and I'm really not sure what kind of compiler it is now.
It sounds like you are compiling as C, not C++. Do your source files have .cpp extension or simply .c? Or may-be in your IDE you have chosen to compile files as C (e.g specified a project to be C project).

11. You do realize that if you divide by already found primes rahter than "all" numbers, you're going to benefit. So keep a list of the primes you've found, and use them to divide by, rather than ALL numbers.

--
Mats

12. Originally Posted by matsp
You do realize that if you divide by already found primes rahter than "all" numbers, you're going to benefit. So keep a list of the primes you've found, and use them to divide by, rather than ALL numbers.

--
Mats
I already did that. What do you think my array is for?

13. I can't even get it to run in cygwin
Code:
```\$ g++ prime_yin.cpp
\$ ./a.exe
This program outputs prime numbers up to a number.