Just wondering, is there anywhere we can join in on the competition, or is it closed?
Just wondering, is there anywhere we can join in on the competition, or is it closed?
Programming Your Mom. http://www.dandongs.com/
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.
Last edited by Differ; 07-31-2007 at 04:17 PM. Reason: UPDATE TO THE CODE
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.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.
Look up a C++ Reference and learn How To Ask Questions The Smart WayOriginally Posted by Bjarne Stroustrup (2000-10-14)
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++.Wait, so it's standard to use lowercase words?
Rather unusual. I tested with the MinGW port of g++ 3.4.2I 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.
Look up a C++ Reference and learn How To Ask Questions The Smart WayOriginally Posted by Bjarne Stroustrup (2000-10-14)
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?
Last edited by Differ; 07-30-2007 at 10:39 PM.
Don't quote me on that... ...seriously
No, uppercase, though you can also use 0.Is null also supposed to be lowercase?
Look up a C++ Reference and learn How To Ask Questions The Smart WayOriginally Posted by Bjarne Stroustrup (2000-10-14)
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).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.
I might be wrong.
Quoted more than 1000 times (I hope).Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
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)
If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
If at first you don't succeed, try writing your phone number on the exam paper.
Same here, only seems to work with GCC on Linux.