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

Comments:

• Patrick - 10 years, 9 months ago

  I know this is trivial with Ruby's Prime class but that would be no fun so I tried to use as little of it as possible. Also I tried to make it valid and 'good' code instead of short code.

  require 'prime'
  def factor(numb)
    unless numb.is_a? Numeric
      raise ArgumentError.new "Please Enter a Number"
    end
    cndt = numb.to_i
    upbound = Math.sqrt(cndt).ceil
    Prime.each(upbound) { |p|
      dividend = cndt / p
      if Prime.prime? dividend
        results = [p, dividend]
        return results
      end
    }
  end
  

  reply permalink

• Anonymous - 10 years, 9 months ago

  I can solve the first problem with some naive Java code in about one second. The 146-bit problem would take too long I think. Any hints?

  import java.math.BigInteger;
  
  class PrimeCracker {
  
      public static void main(String[] args) {
          BigInteger n = new BigInteger("153728883468487");
          BigInteger quot = new BigInteger("2");
          while (n.remainder(quot).compareTo(BigInteger.ZERO) != 0) {
              quot = quot.add(BigInteger.ONE);
          }
          System.out.println(quot + " " + n.divide(quot));
      }
  
  }
  

  reply permalink

• Anonymous - 10 years, 9 months ago

  By the way, the first problem is also easy in J, since it has prime factorisation built-in :P

  q: 153728883468487   NB. => 10850761 14167567
  

  reply permalink

• Max Burstein - 10 years, 9 months ago

  I feel like J has the answer to everything

  reply permalink

• Pyro - 10 years, 9 months ago

  I did this in python (I'm quite new to programming, so there are probably better ways of getting a result).

  I get the two prime numbers that form the 48 bit key, but the program just dosen't work with the second one (It halts). If someone could indicate me where i am failing i would be really happy!!

  def is_prime(n): if n < 2: return False if n in (2, 3): return True if n % 2 == 0 or n % 3 == 0: return False max_divisor = int(n ** 0.5) divisor = 5 while divisor <= max_divisor: if n % divisor == 0 or n % (divisor + 2) == 0: return False divisor += 6 return True

  key=raw_input("key?\n") key=long(key) n1=1 n2=1 Found=False

  while n1<key and Found == False: if is_prime(n1): n2 = key / n1 print n1, n2 if is_prime(n2) and (n2== float(key)/n1): Found == True print "YES! n1=",n1, " n2=", n2 break n1=n1+1

  reply permalink

• Pyro - 10 years, 9 months ago

  Ok i didn't insert the code correctly. Here it is:

  def is_prime(n):
      if n < 2:
          return False
      if n in (2, 3):
          return True
      if n % 2 == 0 or n % 3 == 0:
          return False
      max_divisor = int(n ** 0.5)
      divisor = 5
      while divisor <= max_divisor:
          if n % divisor == 0 or n % (divisor + 2) == 0:
              return False
          divisor += 6
      return True
  
  key=raw_input("key?\n")
  key=long(key)
  n1=1
  n2=1
  Found=False
  
  while n1<key and Found == False:
      if is_prime(n1):
          n2 = key / n1
          print n1, n2
          if is_prime(n2) and (n2== float(key)/n1):
              Found == True
              print "YES! n1=",n1, " n2=", n2
              break
      n1=n1+1
  

  reply permalink

• jjj - 10 years, 9 months ago

  This could literally take hours depending on optimization

  If it worked for the first one I would say it would work for the 2nd just with more time

  reply permalink

• Max Burstein - 10 years, 9 months ago

  You're definitely right that it'll work for the 2nd one. The goal of the second one is to see what optimizations you can make in order to get there quicker. I chose 146bit just because wolframalpha could calculate 144bit in under a minute but wouldn't do 146bit.

  One possible optimization is to refactor the is_prime to use the miller rabin primality test http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test

  You could also look into creating a sieve to cycle through numbers a little quicker http://en.wikipedia.org/wiki/Generating_primes#Prime_sieves

  reply permalink

• jjj - 10 years, 9 months ago

  c# implementation using BigIntegers public LinkedList<BigInteger> factorizer(BigInteger n) { BigInteger two = BigInteger.Abs(2); LinkedList<BigInteger> factors = new LinkedList<BigInteger>(); if ( n.CompareTo(two) < 0) { DisplayText(richTextBox1, "Value needs to be greater than 0", Color.Aquamarine); } while ( (n % two) == (BigInteger.Zero)) { factors.AddLast(two); n = n/2; } if (n.CompareTo(BigInteger.One) > 0) { BigInteger factor = BigInteger.Abs(3); while (factor*(factor).CompareTo(n) <= 0) { if ((n %(factor)) == (BigInteger.Zero)) { factors.AddLast(factor); n = n/factor; } else { factor = factor + 2; } } factors.AddLast(n); } return factors; }

  reply permalink

• jjj - 10 years, 9 months ago

  public LinkedList<BigInteger> factorizer(BigInteger n)
      {
          BigInteger two = BigInteger.Abs(2);
          LinkedList<BigInteger> factors = new LinkedList<BigInteger>();
          if ( n.CompareTo(two) < 0)
          {
              DisplayText(richTextBox1, "Value needs to be greater than 0", Color.Aquamarine);
          }
          while ( (n % two) == (BigInteger.Zero))
          {
              factors.AddLast(two);
              n = n/2;
          }
          if (n.CompareTo(BigInteger.One) > 0)
          {
              BigInteger factor = BigInteger.Abs(3);
              while (factor*(factor).CompareTo(n) <= 0)
              {
                  if ((n %(factor)) == (BigInteger.Zero))
                  {
                      factors.AddLast(factor);
                      n = n/factor;
                  }
                  else
                  {
                      factor = factor + 2;
                  }
              }
              factors.AddLast(n);
          }
          return factors;
      }
  

  reply permalink

• tehMagik - 10 years, 9 months ago

  import math
  
  def CrackKey(key):
      list = sundaram3(math.ceil(math.sqrt(key)))
      for i in list:
          if key % i == 0:
              return i, key / i
  
  def sundaram3(max_n):
      numbers = list(range(3, max_n+1, 2))
      half = (max_n)//2
      initial = 4
  
      for step in range(3, max_n+1, 2):
          for i in range(initial, half, step):
              numbers[i-1] = 0
          initial += 2*(step+1)
  
          if initial > half:
              return [2] + list(filter(None, numbers))
  
  a, b = CrackKey(153728883468487)
  print("A: %d\tB: %d" % (a, b))
  

  reply permalink

• Mre64 - 10 years, 6 months ago

  the worlds longest solution goes to this guy <-- its funny because after i wrote it and ran it i new it would be forever until a result would come out.

  import org.apache.commons.math3.primes.; public class Crack { /* * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub int firstFactor = 0; int secondFactor;

          for(int j = 1; j < 16000000; j++){
              j = Primes.nextPrime(j);
              firstFactor = j;
              System.out.println(j);
              for(int i = 0; i < 16000000; i++){
              i = Primes.nextPrime(i);
              secondFactor = i;
              long multiply = i*j;
              System.out.println(multiply);
  
              if(multiply == 153728883468487L){
                  System.out.println(firstFactor + " * " + secondFactor + " = " + multiply + " gooooooooooooooooooooooooooood!!!");
                  i = 1000000000;
                  j = 1000000000;
              }
          }
      }
  }
  

  }

  reply permalink