
Write a program that reads in an integer from the console and finds all positive prime numbers between 2 and the number. Challenge:Code the routine so that as your program progresses it becomes faster, i.e. it can test the numbers in [1000000, 1000100] faster that it can test the numbers in [1000,1100].

Originally posted by grady
Code the routine so that as your program progresses it becomes faster, i.e. it can test the numbers in [1000000, 1000100] faster that it can test the numbers in [1000,1100]. [/B]
Mathmatically speaking, is that even possible? Doesn't the list of factors that you have to test get longer each time?
It's no slower now than it was when you bought it!

The number of factors does increase, so I'm guessing that perhaps if you want it to speed up you make some way of actually hanging on to your results from the previous number rather than starting over, perhaps taking advantage of the fact that all non prime numbers (bigger than 2) can be expressed as a product of primes.

The phenomena with the speed is a result of a possible solution to this challenge: Find the primes without factoring any numbers.
Last edited by grady; 09122003 at 07:24 PM.

Originally posted by grady
The phenomena with the speed is a result of a possible solution to this challenge: Find the primes without factoring any numbers.
Yep, there's a dynamic programming algorithm to do it.
I don't remember what that algorithm is, of course ( ), but I do remember that it exists...

Ummm.... can we turn this back into a "Programming Challenges" thread? For some reason it has become a "Mathematical Challenges" thread.

here's some sloppy code i had lieing around on prime numbers.
Code:
#!/usr/bin/perl
@numbers[10];
$arrySize = $ARGV[0];
$printSize = $ARGV[1];
$primeCount = 1;
if($arrySize < $printSize){
print "The number of elements to print is larger than the number of elements we want to search through!\n\n";
exit;
}
for($i = 0; $i <= $arrySize; $i++){
$numbers[$i] = $i + 2;
}
for($j = 0; $j <= $arrySize; $j++){
if($numbers[$j] != 0){
for($y = 2; $numbers[$j] * $y <= $arrySize; $y++){
$zeroIndex = $numbers[$j] * $y  2;
$numbers[$zeroIndex] = 0;
}
} # end if
} # end for
print "Here are the prime numbers from 2 through $printSize\n\n";
for($a = 0; $a <= $arrySize && $primeCount <= $printSize; $a++){
if($numbers[$a] != 0 && $numbers[$a] <= $arrySize){
$primeCount++;
print "$numbers[$a] ";
}
}
print "\n";
i was once trapped by windows, but linux set me free...

I'm doing a project for my compy sci class. I'll have three years to work on it. I am going to do it in PHP (so I can make it on my linux box and run it on my teacher's winblows 98 . . . also for the MySQL integration), and I need a good idea for my project. There are seven requirements, that I must show mastery in my program. Almost all of them I could do in my sleep, but I need a good idea.
1. Arrays  Records  Objects
2. Selection Constructs (branching)
3. Iteration Constructs (looping)
4. subprograms (builtin && user defined)
5. parameter passing (hah!)
6. Sorting  Searching Techniques
7. File Access
It looks like a job for MySQL. But what should I make? Any ideas?
Thanks,
TROGDOR!!!
MOUNT TAPE U1439 ON B3, NO RING
Registered Linux user # 31337!

Originally posted by Trogdor
I'm doing a project for my compy sci class. I'll have three years to work on it. I am going to do it in PHP (so I can make it on my linux box and run it on my teacher's winblows 98 . . . also for the MySQL integration), and I need a good idea for my project. There are seven requirements, that I must show mastery in my program. Almost all of them I could do in my sleep, but I need a good idea.
1. Arrays  Records  Objects
2. Selection Constructs (branching)
3. Iteration Constructs (looping)
4. subprograms (builtin && user defined)
5. parameter passing (hah!)
6. Sorting  Searching Techniques
7. File Access
It looks like a job for MySQL. But what should I make? Any ideas?
Thanks,
TROGDOR!!!
three years for that?....hmmmmm......how about a software database program...you know...to keep track of all of the software you own, cd keys....etc....of course...this is probably much too simple for your project...i'm guessing the teacher wants a little more complexity if you're getting three years to write it.

I'm still in high school, so I'm not what you might call a "1337 h4x0r". I'm a year ahead of my compy sci class, so I get three, instead of a little less than two, years to work on this for IB.
I'm thinking something along the lines of web software, so I can upload it to my school's ftp server and access it from any compydore. Maybe something netrelated, like some database access, take input from people, etc.
Here is what I'm thinking:
> SELECT * FROM teachers WHERE clue > 0
0 rows returned
EDIT: Anyone have any good ideas besides bogus SQL requests?
Last edited by Trogdor; 09242003 at 03:35 AM.
MOUNT TAPE U1439 ON B3, NO RING
Registered Linux user # 31337!

EASY one: (sorry another math one)
Print all the squares from 010000 using 2 variables, two additions and 1 while loop. If you can use less, more power to ya!
if (i_forgot && this_is_about_code)
language = c++;

Originally posted by tecknophreak
EASY one: (sorry another math one)
Print all the squares from 010000 using 2 variables, two additions and 1 while loop. If you can use less, more power to ya!
How about no variables, no additions, and no while loop?
Code:
>>> print [x**2 for x in range(int(math.sqrt(10000)))]
[0, 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144,
169, 196, 225, 256, 289, 324, 361, 400, 441,
484, 529, 576, 625, 676, 729, 784, 841, 900,
961, 1024, 1089, 1156, 1225, 1296, 1369, 1444,
1521, 1600, 1681, 1764, 1849, 1936, 2025,
2116, 2209, 2304, 2401, 2500, 2601, 2704,
2809, 2916, 3025, 3136, 3249, 3364, 3481,
3600, 3721, 3844, 3969, 4096, 4225, 4356,
4489, 4624, 4761, 4900, 5041, 5184, 5329,
5476, 5625, 5776, 5929, 6084, 6241, 6400,
6561, 6724, 6889, 7056, 7225, 7396, 7569,
7744, 7921, 8100, 8281, 8464, 8649, 8836,
9025, 9216, 9409, 9604, 9801]

is x**2 the same as saying square x? if so, that's no good, cause then it's using multiplication.
and no using functions, i.e. math.sqrt, cheap.
if (i_forgot && this_is_about_code)
language = c++;

My python attempt:
[code]
x=0
y=0
while y<10000:
y=0
for loop in range(x):
y+=x
print y
x+=1
[code]
mrBen "Carpe Aptenodytes"
Linux User #216794
My blog page
3rd year running  get yourself to LugRadio Live 7th8th July 2007, Wolverhampton, UK. The premier FLOSS community event.

tecknophreak: you underconstrained it
mrBen, that works, here's a properly indented version:
Code:
>>> x = 0; y = 0
>>> while y < 10000:
... y = 0
... for loop in range(x):
... y += x
... print y
... x +=1
...
Posting Permissions
 You may not post new threads
 You may not post replies
 You may not post attachments
 You may not edit your posts

Forum Rules

