Programming Challenges - Page 5


Page 5 of 19 FirstFirst 12345678915 ... LastLast
Results 61 to 75 of 278

Thread: Programming Challenges

  1. #61
    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].

  2. #62
    Join Date
    Mar 2003
    Location
    Wisconsin, USA
    Posts
    256
    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!

  3. #63
    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. #64
    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 07:24 PM.

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

  6. #66
    Join Date
    Mar 2003
    Location
    Tampa, FL USA
    Posts
    2,193
    Ummm.... can we turn this back into a "Programming Challenges" thread? For some reason it has become a "Mathematical Challenges" thread.

  7. #67
    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...

  8. #68
    Join Date
    Sep 2003
    Location
    Edmonton, Alberta, Canada
    Posts
    311
    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!!!
    MOUNT TAPE U1439 ON B3, NO RING

    Registered Linux user # 31337!

  9. #69
    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. #70
    Join Date
    Sep 2003
    Location
    Edmonton, Alberta, Canada
    Posts
    311
    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 03:35 AM.
    MOUNT TAPE U1439 ON B3, NO RING

    Registered Linux user # 31337!

  11. #71
    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!
    if (i_forgot && this_is_about_code)
    language = c++;

  12. #72
    Join Date
    Jan 2000
    Location
    Houston, TX, USA
    Posts
    9,994
    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!
    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]
    We love Sensei!!
    A 1:1 ratio of Arby's sauce to Horsey sauce must be maintained.
    Like Linux? Want to like it more? Try Debian
    Best. (Python.) IRC bot. ever.
    Geekology

  13. #73
    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.
    if (i_forgot && this_is_about_code)
    language = c++;

  14. #74
    Join Date
    Dec 2000
    Location
    Glasgow, Scotland
    Posts
    4,361
    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 7th-8th July 2007, Wolverhampton, UK. The premier FLOSS community event.

  15. #75
    Join Date
    Jan 2000
    Location
    Houston, TX, USA
    Posts
    9,994
    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
    ...
    We love Sensei!!
    A 1:1 ratio of Arby's sauce to Horsey sauce must be maintained.
    Like Linux? Want to like it more? Try Debian
    Best. (Python.) IRC bot. ever.
    Geekology

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •