مساله:
یک عدد طبیعی زمانی 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 countKprimes, count-K-primes, kPrimes) 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;
}
}
