public static void main(String[] args) {

//        double i = 13195 / 29.;
//        System.out.println(i);
//        i = 13195 / 7.;
//        System.out.println(i);
//        i = 13195 / 13.;
//        System.out.println(i);
//        i = 13195 / 5.;
//        System.out.println(i);
//        System.out.println((5 * 7 * 13 * 29));

        try {
            // test the prime utility
//            for (int i = 2; i < 100; i++) {
//                boolean result = isPrime(i);
//                if (result) {
//                    System.out.print(i + ", ");
//                }
//            }

            final long targetNumber = 600851475143L; // 13195; 

            final long start = getFirstPrime();
            final long end = targetNumber;
            final HashMap<Long, Integer> pfs = new HashMap<Long, Integer>();

            int attempts = 0;
            long number = targetNumber;
            while (number >= start) {
                for (long pf = start; pf <= end; pf++) {
                    if (number < start) {
                        break;
                    }
                    attempts++;
                    if (isPrime(pf)) {
                        if (!isDivisible(number, pf)) {
                            continue;
                        } else {
                            int cnt = 1;
                            if (pfs.containsKey(pf)) {
                                cnt += pfs.get(pf);
                            }
                            pfs.put(pf, cnt);
                            number /= pf;
                            System.out.println((attempts) + "\t" + pf + "\t" + number + "\t" + targetNumber);
                        }
                    }
                }
            }

            System.out.println("# prime factors of " + targetNumber);
            final long[] keys = new long[pfs.size()];
            int idx = 0;
            for (long pf : pfs.keySet()) {
                keys[idx++] = pf;
            }
            Arrays.sort(keys);
            for (long pf : keys) {
                System.out.println(pf + "\t" + pfs.get(pf));
            }
        } catch (Exception ex) {
            Logger.getLogger(Problem003.class.getName()).log(Level.SEVERE, null, ex);
        }
    }