Programming Challenges - Page 5

1. Registered User
Join Date
Jul 2003
Posts
28
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].

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?

3. Registered User
Join Date
Jul 2002
Posts
36
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.

4. Registered User
Join Date
Jul 2003
Posts
28
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; 09-12-2003 at 06:24 PM.

5. Registered User
Join Date
Apr 2001
Location
SF Bay Area, CA
Posts
14,947
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...

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

7. 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";```

8. 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 (built-in && 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!!!

9. Registered User
Join Date
Oct 2002
Posts
81
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 (built-in && 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.

10. 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 net-related, like some data-base 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; 09-24-2003 at 02:35 AM.

Join Date
May 2001
Location
Uh, I'm somewhere where I don't know where I am.
Posts
1,228
EASY one: (sorry another math one)

Print all the squares from 0-10000 using 2 variables, two additions and 1 while loop. If you can use less, more power to ya!

12. Originally posted by tecknophreak
EASY one: (sorry another math one)

Print all the squares from 0-10000 using 2 variables, two additions and 1 while loop. If you can use less, more power to ya!

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]```

Join Date
May 2001
Location
Uh, I'm somewhere where I don't know where I am.
Posts
1,228
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.

14. 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]

15. 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
•