A hit of dopamine: prime numbers

Showing posts with label prime numbers. Show all posts

Sunday, September 13, 2009

Euler Problem 49 solution

Time (s): ~0.002

package margusmartseppcode.From_40_to_49;

import java.util.Arrays;

public class Problem_49 {

 // Call only if: (n>0&&(i%2==0||i%3==0||i%5==0||i%7==0))
 static boolean isPrimeS(final int n) {
  final int r = (int) Math.floor(Math.sqrt(n));
  for (int f = 5; f <= r; f += 6)
   if (n % f == 0 || n % (f + 2) == 0)
    return false;
  return true;
 }

 static boolean isPerm(char[] a, char[] b) {
  if (a.length != b.length)
   return false;
  Arrays.sort(a);
  Arrays.sort(b);
  return Arrays.equals(a, b);
 }

 static boolean arePerms(int... n) {
  if (n.length == 0)
   return true;
  for (int i = 1; i < n.length; i++)
   if (!isPerm(("" + n[i - 1]).toCharArray(), ("" + n[i])
     .toCharArray()))
    return false;
  return true;
 }

 static boolean arePrimes(int... n) {
  for (int i : n)
   if (!isPrimeS(i))
    return false;

  return true;
 }

 public static void main(String[] args) {
  int a, b, c;
  a = b = c = 0;

  for (a = 1489;; a += 2) {
   if (a % 3 == 0 || a % 5 == 0 || a % 7 == 0)
    continue;
   
   b = a + 3330;
   c = a + 6660;

   if (arePrimes(a, b, c))
    if (arePerms(a, b, c))
     break;
  }
  System.out.println("" + a + b + c);
 }
}

Euler Problem 47 solution

Time (s): ~0.067

package margusmartseppcode.From_40_to_49;

public class Problem_47 {
 static int unique_factors(int num, int[] primes, int[] factors) {
  int max = (int) Math.sqrt(num);

  for (int i = 0; primes[i] <= max; i++)
   if ((num % primes[i]) == 0) {
    do {
     num /= primes[i];
    } while ((num % primes[i]) == 0);

    return num == 1 ? 1 : factors[num] + 1;
   }

  return 0;
 }

 // creates primes and factors on fly
 public static void main(String[] args) {
  int n = 0, ps = 1, max = 200000;
  int primes[] = new int[max], factors[] = new int[max];

  for (n = 3, primes[0] = 2; n < max; n++)
   if ((factors[n] = unique_factors(n, primes, factors)) == 0) {
    factors[n] = 1;
    primes[ps++] = n;
   } else if ((factors[n] == 4) && (factors[n - 1] == 4)
     && (factors[n - 2] == 4) && (factors[n - 3] == 4))
    break;

  System.out.println(n - 3);
 }
}

Euler Problem 46 solution

Time (s): ~0.030

package margusmartseppcode.From_40_to_49;

public class Problem_46 {
 /** Call only if: (n>0&&(i%2==0||i%3==0||i%5==0||i%7==0)) */
 static boolean isPrimeS(final int n) {
  final int r = (int) Math.floor(Math.sqrt(n));
  for (int f = 5; f <= r; f += 6)
   if (n % f == 0 || n % (f + 2) == 0) return false;
  return true;
 }

 /** Will return array with first nr primes */
 static int[] getPrimes(int nr) {
  if (nr < 0) return new int[0];

  int amount = 0;
  int result[] = new int[nr];

  if (nr > 0) result[amount++] = 2;
  if (nr > 1) result[amount++] = 3;
  if (nr > 2) result[amount++] = 5;
  if (nr > 3) result[amount++] = 7;
  if (nr <= 4) return result;

  for (int i = 9;; i += 2) {
   if (i % 3 == 0 || i % 5 == 0 || i % 7 == 0) continue;
   if (isPrimeS(i)) {
    result[amount++] = i;
    if (amount >= nr) break;
   }
  }
  return result;
 }

 public static void main(String[] args) {
  double tmp = 0;
  int i = 0, num = 3, p[] = getPrimes(1000);

  for (i = 0; !(p[i] > num); i++, tmp = Math.sqrt((num - p[i]) / 2))
   if (tmp == Math.ceil(tmp)) {
    i = 0;
    num += 2;
   }

  System.out.println(num);
 }
}

Time (s): ~0.038

package margusmartseppcode.From_40_to_49;

import java.util.ArrayList;
import java.util.BitSet;

public class Problem_46 {
 /** Sieve of Eratosthenes */
 static Integer[] getSoE(int max) {
  if (max < 1) return new Integer[0];

  BitSet sieve = new BitSet(max / 2);
  ArrayList<Integer> list = new ArrayList<integer>();
  if (max > 1) list.add(2);
  if (max > 2) list.add(3);

  for (int i = 5, f = 1; i <= max; i += 3 - f, f = -f)
   if (sieve.get(i >> 1) == false) {
    for (int add, j = i + (add = i << 1); j < max; j += add)
     sieve.set(j >> 1, true);
    list.add(i);
   }

  return list.toArray(new Integer[0]);
 }

 public static void main(String[] args) {
  double tmp = 0;
  int i = 0, num = 3;
  Integer p[] = getSoE(10000);

  for (i = 0; !(p[i] > num); i++, tmp = Math.sqrt((num - p[i]) / 2))
   if (tmp == Math.ceil(tmp)) {
    i = 0;
    num += 2;
   }

  System.out.println(num);
 }
}

Wednesday, September 9, 2009

Euler Problem 41 solution

Time (s): ~0.009

package margusmartseppcode.From_40_to_49;

import java.util.HashSet;
import java.util.Set;

public class Problem_41 {
 static final int nbrs = 7;

 static boolean isPandigital(String s) {
  return isPandigital(s, nbrs);
 }

 static boolean isPandigital(String s, int nr) {
  if (s.length() != nr)
   return false;

  Set<Character> set = new HashSet<Character>();
  for (int i = 0; i < nr; i++)
   set.add(s.charAt(i));

  if (set.size() != nr)
   return false;
  if (set.contains('0'))
   return false;
  if (set.contains('8'))
   return false;
  if (set.contains('9'))
   return false;
  return true;
 }

 // Call only if: (n>0&&(i%2==0||i%3==0||i%5==0||i%7==0))
 static boolean isPrimeS(final int n) {
  final int r = (int) Math.floor(Math.sqrt(n));
  for (int f = 5; f <= r; f += 6)
   if (n % f == 0 || n % (f + 2) == 0)
    return false;
  return true;
 }

 public static void main(String[] args) {
  int i;
  for (i = 7654321; i >= 1234567; i -= 2) {
   if (i % 3 == 0 || i % 5 == 0 || i % 7 == 0)
    continue;
   if (!isPrimeS(i))
    continue;
   if (isPandigital("" + i))
    break;
  }
  System.out.println(i);
 }
}

Euler Problem 37 solution

Time (s): ~0.599

package margusmartseppcode.From_30_to_39;

import java.io.File;
import java.io.FileNotFoundException;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Problem_37 {

 static Integer cint(String nr) {
  return Integer.parseInt(nr);
 }

 static boolean isLTP(String mem, Set<Integer> primes) {
  int n = mem.length();
  if (n < 1)
   return true;
  return primes.contains(cint(mem)) && isLTP(mem.substring(1), primes);
 }

 static boolean isRTP(String mem, Set<Integer> primes) {
  int n = mem.length();
  if (n < 1)
   return true;
  return primes.contains(cint(mem))
    && isRTP(mem.substring(0, n - 1), primes);
 }

 static boolean isTP(String mem, Set<Integer> primes) {
  return isLTP(mem, primes) && isRTP(mem, primes);
 }

 private static void bTP(Integer mem, Set<Integer> primes,
   Set<Integer> truncatable) {
  if (primes.contains(mem)) {
   if (isTP(""+mem, primes))
    truncatable.add(mem);
   TruncatablePrimes(mem, primes, truncatable);
  }
 }

 private static void TruncatablePrimes(Integer elem, Set<Integer> primes,
   Set<Integer> truncatable) {
  String[] o = new String[] { "1", "2", "3", "4", "5", "6", "7", "8", "9" };
  String s = "" + elem;

  for (String pos : o) {
   bTP(cint(s + pos), primes, truncatable);
   bTP(cint(pos + s), primes, truncatable);
  }
 }

 public static void main(String[] args) throws FileNotFoundException {
  Set<Integer> truncatable = new HashSet<Integer>();
  Set<Integer> primes = new HashSet<Integer>();
  Scanner sc = new Scanner(new File("primes1m.txt"));
  int sum = 0;

  for (String tmp = sc.next(); sc.hasNext(); tmp = sc.next())
   primes.add(Integer.parseInt(tmp));

  for (Integer elem : new Integer[] { 3, 7 })
   TruncatablePrimes(elem, primes, truncatable);

  for (Integer elem : truncatable)
   sum += elem;

  System.out.println(sum);
 }
}

Euler Problem 35 solution

Time (s): ~0.921

package margusmartseppcode.From_30_to_39;

import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Problem_35 {
 static boolean contains_024568(final char[] input) {
  int n = input.length;
  for (int i = 4; i < n; i++)
   if (input[i] == '0' || input[i] == '2' || input[i] == '4'
     || input[i] == '5' || input[i] == '6' || input[i] == '8')
    return true;
  return false;
 }

 static void rotate(StringBuilder sb) {
  sb.append(sb.charAt(0)).delete(0, 1);
 }

 static int iRotate(StringBuilder s) {
  return Integer.parseInt(s.append(s.charAt(0)).delete(0, 1).toString());
 }

 static void CircularPrimes(Integer elem, Set<Integer> primes,
   Set<Integer> found, Set<Integer> circular) {
  StringBuilder sb = new StringBuilder("" + elem);
  ArrayList<Integer> tmp = new ArrayList<Integer>();
  int n = sb.length(), i;

  if (found.contains(elem) || circular.contains(elem))
   return;
  for (i = 1; i <= n; i++)
   tmp.add(iRotate(sb));
  for (Integer mem : tmp)
   if (!primes.contains(mem)) {
    found.addAll(tmp);
    return;
   }

  circular.addAll(tmp);
 }

 public static void main(String[] args) throws FileNotFoundException {
  Set<Integer> circular = new HashSet<Integer>();
  Set<Integer> primes = new HashSet<Integer>();
  Set<Integer> found = new HashSet<Integer>();
  Scanner sc = new Scanner(new File("primes1m.txt"));

  for (String tmp = sc.next(); sc.hasNext(); tmp = sc.next())
   if (!contains_024568(tmp.toCharArray()))
    primes.add(Integer.parseInt(tmp));

  for (Integer elem : primes)
   CircularPrimes(elem, primes, found, circular);

  System.out.println(circular.size());
 }
}

Tuesday, September 8, 2009

Euler Problem 27 solution

Time (s): ~0.034

package margusmartseppcode.From_20_to_29;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class Problem_27 {
 static Integer prime_k[] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37,
   41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107,
   109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179,
   181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251,
   257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331,
   337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409,
   419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487,
   491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577,
   587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653,
   659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743,
   751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829,
   839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929,
   937, 941, 947, 953, 967, 971, 977, 983, 991, 997 };

 public static void main(String[] args) {
  int nmax = 0, n, pr = 0;
  Set<Integer> set = new HashSet<Integer>(Arrays.asList(prime_k));

  for (int i = -999; i < 999; i += 2)
   for (int b : prime_k) {
    n = 1;
    while (set.contains(n * n + i * n + b))
     n += 1;
    if (n > nmax) {
     nmax = n;
     pr = i * b;
    }
   }
  System.out.println(pr);
 }
}

Euler Problem 26 solution

Time (s): ~0.021

package margusmartseppcode.From_20_to_29;

public class Problem_26 {
 // Brent's algorithm
 public static void main(String[] args) {
  int r = 1, c = 0, power, lam, t, tr, h, hr;
  for (int i = 999; i > 1; i--) {
   power = lam = 1;
   tr = (1 % i) * 10;
   hr = (tr % i) * 10;
   t = 1 / i;
   h = tr / i;

   while (t != h || tr != hr) {
    if (power == lam) {
     t = h;
     tr = hr;
     power *= 2;
     lam = 0;
    }
    h = hr / i;
    hr = (hr % i) * 10;
    lam++;
   }
   if (lam > c) {
    c = lam;
    r = i;
   }
  }
  System.out.println(r);
 }
}

Euler Problem 23 solution

Time (s): ~0.231

package margusmartseppcode.From_20_to_29;

public class Problem_23 {
 public static boolean IsAbundant(int num) {
  int factorSum = 1;
  double temp = Math.sqrt(num);

  if (temp % 1 == 0)
   factorSum -= temp;
  for (int i = 2; i <= temp; i++)
   if (num % i == 0)
    factorSum += i + num / i;

  if (factorSum > num)
   return true;

  return false;
 }

 public static void main(String[] args) {
  final int size = 28123;
  int[] d = new int[8192];
  int[] not = new int[size];
  int c = 0, c2 = 0, sum = 0;

  for (int i = 10; i <= size; i++)
   if (IsAbundant(i))
    d[c++] = i;

  for (int i = 0; i < c; i++)
   for (int j = i; j < c; j++)
    if ((c2 = d[i] + d[j]) < size)
     not[c2] = 1;

  for (int i = 1; i < size; i++)
   if (not[i] != 1)
    sum += i;

  System.out.println(sum);
 }
}

Euler Problem 10 solution

Time (s): ~0.097

package margusmartseppcode.From_10_to_19;

import java.util.BitSet;

public class Problem_10 {
 /** Sieve of Eratosthenes sum */
 static long getSoEsum(int max) {
  if (max < 1)
   return 0;
  BitSet sieve = new BitSet(max / 2);
  long sum = (max > 1 ? 2 + (max > 2 ? 3 : 0) : 0);

  for (int i = 5, f = 1; i <= max; i += 3 - f, f = -f)
   if (sieve.get(i >> 1) == false) {
    int add = i << 1;
    for (int j = i + add; j < max; j += add)
     sieve.set(j >> 1, true);
    sum += i;
   }

  return sum;
 }

 public static void main(String[] args) {
  System.out.println(getSoEsum(2000000));
 }
}

Euler Problem 7 solution

Time (s): ~0.011

package margusmartseppcode.From_1_to_9;

import java.util.BitSet;

public class Problem_7 {
 static long getSoExnt(int max, int nr) {
  if (max < 1 || nr < 1 || max < nr)
   return -1;
  if (nr < 4)
   return (nr == 1 ? 2 : (nr == 2 ? 3 : 5));
  BitSet sieve = new BitSet(max / 2);

  for (int i = 5, f = 1, c = 2; i <= max; i += 3 - f, f = -f)
   if (sieve.get(i >> 1) == false) {
    int add = i << 1;
    for (int j = i + add; j < max; j += add)
     sieve.set(j >> 1, true);
    if (++c >= nr)
     return i;
   }

  return -1;
 }

 public static void main(String[] args) {
  System.out.println(getSoExnt(120000, 10001));
 }
}

Euler Problem 3 solution

Time (s): ~0.001

package margusmartseppcode.From_1_to_9;

public class Problem_3 {
 static long lpf(long nr) {
  long max = 0;

  for (long i = 2; i <= nr / i; i++)
   while (nr % i == 0) {
    max = i;
    nr = nr / i;
   }

  return nr > 1 ? nr : max;
 }

 public static void main(String[] args) {
  System.out.println(lpf(600851475143L));
 }
}

Pages

Sunday, September 13, 2009

Wednesday, September 9, 2009

Tuesday, September 8, 2009