Just wondering, is there anywhere we can join in on the competition, or is it closed?
Printable View
Just wondering, is there anywhere we can join in on the competition, or is it closed?
It's closed. Sorry.
I have no clue what sieves are, so sorry about that too. =\
The principle of smn and imn are thatCode://////////
//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 % small)) //seeing if increm is divisible by small
{
//sets cor to 0
cor = false;
//updates the array
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;
//updates the array
for (acrem = increm * 3 / 2; acrem <= alim; acrem += increm)
array[acrem] = false;
}
cor = true;
}
}
cout << '\n';
}
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.
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.Quote:
I have no clue what sieves are, so sorry about that too. =\
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.
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% faster.
Yes, in C++.Quote:
Wait, so it's standard to use lowercase words?
Rather unusual. I tested with the MinGW port of g++ 3.4.2Quote:
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.
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?
No, uppercase, though you can also use 0.Quote:
Is null also supposed to be lowercase?
NULL is a define, not a keyword.
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).Quote:
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.
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 can't even get it to run in cygwin
I was going to time mine against yours.Code:$ g++ prime_yin.cpp
$ ./a.exe
This program outputs prime numbers up to a number.
Please insert that number.
100
2
23224 [main] a 3140 _cygtls::handle_exceptions: Error while dumping state (probably corrupted stack)
Segmentation fault (core dumped)
Same here, only seems to work with GCC on Linux.