k-Primes

kata programming

مساله:

یک عدد طبیعی زمانی k-prime گفته می شود که دقیقا k عامل اصلی داشته باشد. برای مثال:

k = 2  -->  4, 6, 9, 10, 14, 15, 21, 22, ...
k = 3  -->  8, 12, 18, 20, 27, 28, 30, ...
k = 5  -->  32, 48, 72, 80, 108, 112, ...

یک عدد طبیعی اول است اگر و فقط اگر 1prime باشد.

وظیفه:

تابع count_Kprimes را کامل کنید به طوری که پارامترهای k, start, end را بگیرد و یک آرایه از k-prime بین start و end برگرداند.

مثال:

countKprimes(5, 500, 600) --> [500, 520, 552, 567, 588, 592, 594]

وظیفه بعدی: پازل

عدد مثبت s را بگیرید،‌ تعداد کل راه حل های معادله a + b + c = s را بیابید، به طوری که a یک 1-prime و b یک 3-prime و c یک 7-prime میباشد.

نام تابع را puzzle(s) بنامید.

puzzle(138)  -->  1  because [2 + 8 + 128] is the only solution
puzzle(143)  -->  2  because [3 + 12 + 128] and [7 + 8 + 128] are the solutions

Description:

A natural number is called k-prime if it has exactly k prime factors, counted with multiplicity. For example:

k = 2  -->  4, 6, 9, 10, 14, 15, 21, 22, ...
k = 3  -->  8, 12, 18, 20, 27, 28, 30, ...
k = 5  -->  32, 48, 72, 80, 108, 112, ...

A natural number is thus prime if and only if it is 1-prime.

Task:

Complete the function count_Kprimes (or countKprimescount-K-primeskPrimes) which is given parameters k, start, end (or nd) and returns an array (or a list or a string depending on the language – see “Solution” and “Sample Tests”) of the k-primes between start (inclusive) and end (inclusive).

Example:

countKprimes(5, 500, 600) --> [500, 520, 552, 567, 588, 592, 594]

Notes:

The first function would have been better named: findKprimes or kPrimes 🙂

In C some helper functions are given (see declarations in ‘Solution’).

For Go: nil slice is expected when there are no k-primes between start and end.


Second Task: puzzle (not for Shell)

Given a positive integer s, find the total number of solutions of the equation a + b + c = s, where a is 1-prime, b is 3-prime, and c is 7-prime.

Call this function puzzle(s).

Examples:

puzzle(138)  -->  1  because [2 + 8 + 128] is the only solution
puzzle(143)  -->  2  because [3 + 12 + 128] and [7 + 8 + 128] are the solutions

import java.util.stream.LongStream;

public class KPrimes {

    public static long nPrime(long n) {
        int result = 0;

        for (long i = 2 ; i < Math.sqrt(n)+1 ; ++i) {
            while (n%i == 0) {
                result++;
                n /= i;
            }
        }

        if (n > 1)
            result++;

        return result;
    }

    public static long[] countKprimes(int k, long start, long end) {
        return LongStream.range(start, end+1).filter(x -> nPrime(x) == k).toArray();
    }

    public static int puzzle(int s) {
        int result = 0;

        for (long i : countKprimes(1, 1, s)) {
            for (long j : countKprimes(3, 1, s)) {
                for (long k : countKprimes(7, 1, s)) {
                    if (i + j + k == s)
                        result++;
                }
            }
        }

        return result;
    }
}
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
import java.util.stream.LongStream;

public class KPrimes {
  public static long[] countKprimes(int k, long start, long end) {
    return LongStream.rangeClosed(start, end)
        .filter(n -> primeFactors(n, k) == k)
        .toArray();
  }
  
  /**
   * Returns the number of prime factors "k", or maxk + 1 when k > maxk.
   */
  private static int primeFactors(long n, final int maxk) {
    int k = 0;
    while (n > 1 && (n & 1) == 0) {
      k += 1;
      n >>= 1;
      if (k > maxk) {
        return k;
      }
    }
    long t = 3;
    while (t <= (long) Math.sqrt(n)) {
      if (n % t == 0) {
        n /= t;
        k += 1;
      } else {
        t += 2;
      }
    }
    if (n > 1) {
      k += 1;
    }
    return k;
  }
  
  /**
   * Returns the count of permutations of (a, b, c) satisfying (a + b + c = s), where a b and c are elements of the sets
   * containing integers with 1, 3, and 7 prime factors respectively.
   * <p>
   * Time complexity is that of finding prime facto\rs of numbers up to s. Call this O(f()), O(f()) > O(s). The rest is
   * O(c * g() * loga), g() = average size of window into b. O(g()) <= O(b). So, time complexity is based on density of
   * these types of composites and primes. Performance may be improved usin ga modified Sieve of Eratosthenes that
   * counts prime factors.
   */
  public static int puzzle(int s) {
    final List<List<Integer>> abc = findABC(s);
    if (abc.size() < 3) {
      return 0;
    }
    final int[] aArray = abc.get(0).stream().mapToInt(n -> n).toArray();
    final int amin = aArray[0];
    final int amax = aArray[aArray.length - 1];
    int bs = 0;  // Window into b, open range [bs, be).
    int be = 0;
    int count = 0;
    for (final int cv : abc.get(2)) {
      final int bmin = s - cv - amax;
      final int bmax = s - cv - amin;
      final List<Integer> b = abc.get(1);
      while (bs < b.size() && b.get(bs) < bmin) {
        bs += 1;
      }
      while (be < b.size() && b.get(be) <= bmax) {
        be += 1;
      }
      for (int bi = bs; bi < be; bi++) {
        final int bv = b.get(bi);
        final int agoal = s - bv - cv;
        final int abins = Arrays.binarySearch(aArray, agoal);
        if (abins >= 0) {
          count += 1;
        }
      }
    }
    return count;
  }
  
  private static List<List<Integer>> findABC(int s) {
    return IntStream.range(2, s)
        .boxed()
        .collect(Collectors.groupingBy(n -> primeFactors(n, 7)))
        .entrySet().stream()
        .filter(e -> e.getKey() == 1 || e.getKey() == 3 || e.getKey() == 7)
        .sorted(Comparator.comparingInt(e -> e.getKey()))
        .map(e -> e.getValue())
        .collect(Collectors.toCollection(ArrayList::new));
  }
}
import java.util.*;
import java.util.stream.LongStream;
public class KPrimes {
    
   public static long nPrime(long n) {
        int result = 0;
        for (long i = 2 ; i < Math.sqrt(n)+1 ; ++i) {
            while (n%i == 0) {
                result++;
                n /= i;
            }
        }
        if (n > 1) result++;
        return result;
    }
    public static long[] countKprimes(int k, long start, long end) {
        return LongStream.range(start,end+1).filter(x -> nPrime(x)==k).toArray();
    }
    public static int puzzle(long s) {
      int count = 0;

      for (long c : countKprimes(1, 1, s)) {
        for (long b : countKprimes(3, 1, s)) {
          for (long a : countKprimes(7, 1, s)) {
            if (a + b + c > s) {
              break;
            }
            if (a + b + c == s) {
              count++;
            }
          }
        }
      }
    
      return count;
    }
}
public class KPrimes {
    
    public static long[] countKprimes(int k, long start, long end) {
        
        int maxSolCnt = (int) ( end - start + 1 );
        long[] solutions = new long[maxSolCnt];
        int cntSolutions = 0;
        
        for (long n=start; n<=end; n++) {
          if ( isKPrime(k, n) ) {
            solutions[cntSolutions++] = n;
          }
        }
      
        long[] res = new long[cntSolutions];
        for (int i=0; i<cntSolutions; i++)
          res[i] = solutions[i];
         
        return res;
    }
    public static int puzzle(int s) {
        
        int cnt = 0;
        
        for (int a=2; a<s; a++)
          for (int b=2; b<s; b++)
            for (int c=2; c<s; c++)
              if ( a + b + c == s && isKPrime( 1, a ) && isKPrime( 3, b ) && isKPrime( 7, c ) )
                cnt++;
        
        return cnt;
    }
    
    // -= My Methods =-
    
    private static boolean isPrime(long num) {
      long m1 = 1;
      long m2 = num;
      do {
        m2 = num / ++m1;
      } while ( num % m1 != 0 && m1 <= m2 );
      return m1 > m2;
    }
    
    private static boolean isKPrime(int k, long num) {
    
      if ( k < 1 )
        return false;
      if ( isPrime( num ) )
        return ( k == 1 );
      
      // - prime factors -
      
      long[] primeFactors = new long[k];
      int cntFactors = 0;
      
      long m1 = 1;
      long m2 = num;
      while ( cntFactors <= k ) {
        m1++;
        m2 = num / m1;
        if ( m1 > m2 )
          break;
        if ( num % m1 == 0 ) {
          if ( isPrime(m1) ) {
            if ( cntFactors < k )
              primeFactors[cntFactors] = m1;
            cntFactors++;
          }
          if ( m1 != m2 && isPrime(m2) ) {
            if ( cntFactors < k )
              primeFactors[cntFactors] = m2;
            cntFactors++;
          }
        }
      }
      
      if ( cntFactors > k )
        return false;
      
      // - solution -
      
      long sol = 1;
      
      int[] solIndx = new int[k];
      for (int i=0; i<k; i++) {
        solIndx[i] = 0;
        sol *= primeFactors[0];
      }
      
      m1:
      while ( sol != num ) {
        
        // - next solution -
        for (int i=0; i<k; i++) {
          if ( ++solIndx[i] < cntFactors )
            break;
          solIndx[i] = 0;
          
          if ( k - i == 1 )
            break m1;
        }
        
        sol = 1;
        for (int i=0; i<k; i++)
          sol *= primeFactors[solIndx[i]];
      }
      
      return sol == num;
    }
}
import java.util.stream.LongStream;

public class KPrimes {
    
    public static long[] countKprimes(int k, long start, long end) {
        return LongStream.rangeClosed(start, end)
            .filter(n -> findK(n) == k)
            .toArray();
    }
    
    public static int puzzle(long s) {
      int count = 0;

      for (long c : countKprimes(1, 1, s)) {
        for (long b : countKprimes(3, 1, s)) {
          for (long a : countKprimes(7, 1, s)) {
            if (a + b + c > s) {
              break;
            }
            if (a + b + c == s) {
              count++;
            }
          }
        }
      }
      
      return count;
    }
    
    private static long findK(long n) {
      int myK = 0;
      
      // Deal with zero
      if (n == 0) {
        return 0;
      }

    // Factor out all twos
    if (n % 2 == 0) {
      myK++;
      n = n / 2;
      while (n % 2 == 0) {
        myK++;
        n = n / 2;
      }
    }

    // Factor out other primes
    long factor = 3;
    while (Math.abs(n) > 1 && factor <= Math.sqrt(n)) {
      if (n % factor == 0) {
        myK++;
        n = n / factor;
        while (n % factor == 0) {
          myK++;
          n = n / factor;
        }
      }
      factor += 2;
    }

    // number is prime
    if (n != 1) {
      myK++;
    }
      
      return myK;
    }

}

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *