Problem of the Day
A new programming or logic puzzle every Mon-Fri

Comments:

• David - 9 years ago

  Python with a touch of feature creep.

  from math import sqrt
  import time
  
  debug = 0
  
  start_time = time.time()
  
  
  def list_primes(largest_int):
      if(largest_int < 2):
          return []
      if(largest_int == 2):
          return [2]
      if(largest_int < 5):
          return [2, 3]
      if(largest_int > 50000):
          print "Sorry, %d is just too big to run through this algorithm" % largest_int
          return []
      if(largest_int > 2500):
          factors = list_primes(int(sqrt(largest_int))+1)
      else:
          factors = range(2, int(sqrt(largest_int))+1)
      nums = range(2, largest_int)
      if(debug):
          print largest_int
      for i in factors:
      # for i in range(2, 7):
          nums = filter(lambda x: x==i or x%i, nums)
      return nums
  
  
  
  print -1, list_primes(-1)
  print 0, list_primes(0)
  print 1, list_primes(1)
  print 2, list_primes(2)
  print 3, list_primes(3)
  print 4, list_primes(4)
  print 5, list_primes(5)
  print 6, list_primes(6)
  print 50, list_primes(50)
  print 50000, list_primes(50000)
  
  print int(sqrt(5))
  
  
  
  
  
  print "ExecutionTime %f seconds" % (time.time() - start_time)
  

  reply permalink

• Jack le - 9 years ago

  This was actually an assignment in my system level programming class. The program is actually to solve project euler 10.

  #include <stdio.h>

  int main(){ // This program uses the sieve of Eratosthenes to solve the problem. int numbers[2000000] = {}; //Create an array of 2000000 integers of value 0 long int sum = 0; // Initialize sum to 0 // Create i and j for the nested for loops, they have to be long int because j*j will exceed the limit of int at some point long int i, j; for(j = 2; j <= sizeof(numbers)/4; j++){ // j goes from 2 to n if(!numbers[j-1]){ // If the number is not marked sum += j; // That is a prime number and add it to sum for(i = j*j; i <= sizeof(numbers)/4; i+=j) // Mark all the numbers from j² to the end by j interval numbers[i-1] = 1; } } printf("sum: %ld\n",sum); // Display the sum return 0; }

  reply permalink

• Werner D - 9 years ago

  C# solution:

          public static List<int> Sieve(int largestInt)
          {
              List<int> primes = new List<int>();
              List<int> matrix = new List<int>();
              for (int i = 2; i <= largestInt; i++)
                  matrix.Add(i);
  
              while (matrix.Count > 0)
              {
                  int p = matrix[0];
                  primes.Add(p);
  
                  for (int x = p; x <= matrix[matrix.Count - 1]; x++)
                  {
                      if (x % p == 0)
                          matrix.Remove(x);
  
                      if (matrix.Count == 0)
                          break;
                  }
              }
  
              return primes;
          }
  

  reply permalink

• Anonymous - 9 years ago

  I've run this with up to 10 million which takes about a minute. Haven't tried 100 million.

  #python 2.7
  n = int(raw_input("Enter a number to find primes> "))
  
  sieve_array = []
  for i in range(n+1):
      sieve_array.append(i)
  
  sieve_array[1] = 0
  prime_array = []
  
  c = 2
  while c < n:
      m = 2
  
      while c*m <= n:
          sieve_array[c*m] = 0
          m = m + 1
      c = c + 1
  
  for item in sieve_array:
      if item != 0:
          prime_array.append(item)
  
  print prime_array
  print "There are %d primes between 1 and %d" % (len(prime_array), n)
  

  reply permalink