代码之家 › 专栏 › 技术社区 › Oleg Cherednik

计算给定范围内的半素数[a..b]

performance algorithm java

-1

Oleg Cherednik · 技术社区 · 7 年前

我正在解决可变性问题 CountSemiprimes: Count the semiprime numbers in the given range [a..b] .

任务描述

首要的 是一个正整数X,正好有两个不同的因子:1和X。前几个素整数是2、3、5、7、11和13。

A. 半素数 是一个自然数,它是两个(不一定不同)素数的乘积。前几个半素数是4,6,9,10,14,15,21,22,25,26。

给出了两个非空数组P和Q,每个数组由M个整数组成。这些数组表示关于指定范围内半素数数量的查询。

查询K要求您查找范围(P[K],Q[K])内的半素数,其中1·P[K]·Q[K]·N。

为以下假设编写有效的算法:

N是[1..50000]范围内的整数;
M是[1..30000]范围内的整数;
数组P,Q的每个元素都是[1..N]范围内的整数; P[i]–Q[i]。

我的解决方案

所有最大范围

测试表明,它应该需要2秒,但我的解决方案需要7秒。

这是我目前的解决方案

class Solution {
    private static List<Integer> getPrimes(int max) {
        List<Integer> primes = new ArrayList<>(max / 2);

        for (int i = 0; i < max; i++)
            if (isPrime(i))
                primes.add(i);

        return primes;
    }

    private static boolean isPrime(int val) {
        if (val <= 1)
            return false;
        if (val <= 3)
            return true;

        for (int i = 2, sqrt = (int)Math.sqrt(val); i <= sqrt; i++)
            if (val % i == 0)
                return false;

        return true;
    }

    private static boolean[] getSemiPrimes(int N) {
        List<Integer> primes = getPrimes(N);
        boolean[] semiPrimes = new boolean[N + 1];

        for (int i = 0; i < primes.size(); i++) {
            if (primes.get(i) > N)
                break;

            for (int j = i; j < primes.size(); j++) {
                if (primes.get(j) > N || N / primes.get(i) < primes.get(j))
                    break;

                int semiPrime = primes.get(i) * primes.get(j);

                if (semiPrime <= N)
                    semiPrimes[semiPrime] = true;
            }
        }

        return semiPrimes;
    }

    public static int[] solution(int N, int[] P, int[] Q) {
        boolean[] semiPrimes = getSemiPrimes(N);
        int[] res = new int[P.length];

        for (int i = 0; i < res.length; i++)
            for (int j = P[i]; j <= Q[i]; j++)
                if (semiPrimes[j])
                    res[i]++;

        return res;
    }
}

关于提高绩效有什么想法吗?我的最后一个问题是删除 Set

2 回复 | 直到 7 年前

Paul Hankin 7 年前

您可以预计算大小为N+1的数组A,该数组在A[i]处存储小于或等于i的半素数。然后是一个问题 p, q A[q] - A[p-1] .

这个数组可以有效地计算:设P是一个小于或等于N/2的素数数组。然后(在类似java的伪代码中):

A = new int[N+1]
for (int p : P) {
  for (int q : P) {
      if (p*q > N || q > p) break;
      A[p*q] = 1
  }
}

for (int i = 1; i <= N; i++)
    A[i] += A[i-1]

这是通过使用 1 在数组中,然后获取累积和。它在优于O(N^2)和低于O(N)的时间内运行——大约有 N/2logN P P 使用Erastothenes筛取O(N log N)。

这个程序的Python版本需要0.07秒来预计算 A 对于 N=50000 ,并执行30000个查询。当在codility上运行时,它得到满分(100),codility报告它检测到代码的复杂性为O(N log(log(N))+M)。

STaefi Hitesh 7 年前

得分为100%的Java解决方案如下:

找出其乘积不大于的素数集 N
将它们作为0和1的逐位数组创建半素数
创建半素数的前缀和
P[i] 到 Q[i] 在里面 O(M)

整个算法是有效的 O(N * log(log(N)) + M) 由Codibility的测试结果评估说明。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class CountSemiPrime {

    public static void main(String[] args) {
        int[] P = new int[] {1, 4, 16};
        int[] Q = new int[] {26, 10, 20};
        System.out.println( Arrays.toString( new CountSemiPrime().solution( 26, P, Q ) ) );
    }

    public int[] solution(int N, int[] P, int[] Q) {

        Integer[] primes = sieve(N/2+1);

        int[] temp = new int[N+1];
        for (int i = 0; i < primes.length; i++) {
            for (int j = 0; j < primes.length; j++) {
                int semiPrime = primes[i] * primes[j];
                if(semiPrime <= N)
                    temp[semiPrime] = 1;
            }
        }

        int[] prefix = new int[N+1];
        for (int i = 1; i < temp.length; i++) {
            prefix[i] = temp[i] + prefix[i-1];
        }

        int[] retVal = new int[P.length];
        for (int i = 0; i < retVal.length; i++) {
            retVal[i] = prefix[Q[i]] - prefix[P[i]-1];
        }

        return retVal; 
    }


    public Integer[] sieve(int n) {

        boolean[] temp = new boolean[n+1];
        for (int i = 0; i < temp.length; i++) {
            temp[i] = true;
        }
        temp[0] = temp[1] = false;

        int i = 2;
        while (i * i <= n) {
            removeProducts( temp, i );
            i++;
        }

        List<Integer> ret = new ArrayList<>();
        for (int j = 0; j < temp.length; j++) {
            if(temp[j])
                ret.add( j );
        }

        return ret.toArray( new Integer[ret.size()] );
    }

    private void removeProducts(boolean[] temp, int i) {
        for (int j = i*i; j < temp.length; j++) {
            if(temp[j] && j % i == 0) {
                temp[j] = false;
            }
        }
    }
}

Mike Belyakov 7 年前

Ruby 100%溶液

require 'prime'
require 'set'

def solution(n, p, q)
    primes = Prime::EratosthenesGenerator.new.take_while {|i| i <= n/2 }
    sqrt = Math.sqrt(n)
    semiprimes = primes.each_with_index.inject(Set.new) do |acc, (e,i)|
      break acc if e > sqrt.to_i
      primes[i..-1].each{ |pr| e*pr > n ? break : acc << e*pr }
      acc
    end
    offsets = semiprimes.sort.each_with_index.inject([]) {|acc,(el,i)| acc[el] = i+1;acc  }

    p.each_with_index.inject([]) do |acc, (el,i)|
      next acc << 0 unless offsets[el..q[i]]

      left =  offsets[el..q[i]].detect{|a| a}
      next acc << 0 unless left

      right = offsets[el..q[i]].reverse_each.detect{|a| a}

      acc << ((left..right).size)
    end
end

4Rom1 5 年前

我的解决方案使用Eratosthenes筛子,使得数N的最小素数因子存储在数组因子[N]中。然后,如果Factor[N/Factor[N]]=0,我们有一个半素数递增一个和扫描。 A[r]=包括性扫描[Q[r]]-包括性扫描[P[r]-1]。

(100% task score) :

def solution(N, P, Q):
 A=len(P)*[0]
 if N<4:
     return A
#Minimum prime factor of n stored in Factor[n]
 Factor = [0] * (N + 1)
 i = 2
 while (i * i <= N):
  if (Factor[i] == 0):
   k = i * i
   while (k <= N):
    if (Factor[k] == 0):
     Factor[k] = i;
    k += i
  i += 1
#Count semi prime numbers and store 
#sum scan in array Incluse_scan   
 Incluse_scan=[0] * (N + 1)
 cnt_semi=0
 for k in range(4,N+1):
     if Factor[k]!=0:
         d=int(k/Factor[k])
         if Factor[d]==0:
             cnt_semi+=1                 
     Incluse_scan[k]=cnt_semi   
#Do the difference of semi prime counters
 for r in range(0,len(P)):
     if(P[r]<=4):
       min_inclusive=0
     else:
       min_inclusive=P[r]-1 
     A[r]=Incluse_scan[Q[r]]-Incluse_scan[min_inclusive] 
 return A

Behrouz.M 5 年前

github 在cpp中:


vector<int> getFactArr(int n) {
    vector<int> f(n+1, 0);
    f[1] = 1;
    int i = 2;
    while (i * i <= n) {
        if (f[i] == 0) {
            int k = i * i;
            while (k <= n) {
                if (f[k] == 0)
                    f[k] = i;
                k+=i;
            }
        }
        i++;
    }

    return f;
}

vector<int> solution(int N, vector<int> &P, vector<int> &Q) {
    vector<int> F = getFactArr(N);
    vector<int> prefix_semi_primes(N + 1, 0);

    for (int x = 1; x <= N; x++) {
        if (F[x] > 0 && F[x / F[x]] == 0)
            prefix_semi_primes[x]++;
        prefix_semi_primes[x] += prefix_semi_primes[x - 1];
    }

    const int M = P.size();
    vector<int> ans(M, 0);
    for (int i = 0; i < M; i++) {
        ans[i] = prefix_semi_primes[Q[i]] - prefix_semi_primes[P[i] - 1];
    }

    return ans;
}

Lavish Kothari 7 年前

这是一个有趣的问题。我试过了,得到了88%的分数。

以下是我的策略:

Sieve of Eratosthenes 为了得到一个 BitSet 对于素数。
现在我绕了一圈把所有的素数加在一个 primeList .
我寻找半素数的策略有点有趣,我逐渐地达到了这个策略。

private static boolean isSemiPrime(int n) {
    if(n==1 || n==0 || primeBitSet.get(n))
        return false;
    int firstFactor = findFirstFactor(n);
    if(firstFactor==0 || firstFactor==1)
        return false;
    return isPrime(n / firstFactor);
}

private static int findFirstFactor(int n) {

    for (int i = 0; i < primeList.size(); i++) {
        if (n % primeList.get(i) == 0)
            return primeList.get(i);
    }
    // should never be the case
    return 0;
}

我不太清楚为什么我得了88%的分数。(我错过了什么)

但最有趣和值得注意的部分是检查给定数字是否为半素数的策略:

求给定数的第一个素数因子
然后检查给定数和第一个素数因子的商是否为素数。
如果它是素数,那么给定的数是半素数,否则给定的数不是半素数。

x . 一次填充此数组并回答中的每个查询 O(1)

与解决方案无关,但与我的 Task Score 为88%, Correctness 100%和 Performance 80%. 我会很高兴听到建议和我错过的任何东西。

希望这有帮助。:)

sath 7 年前

const isSemiPrime = (num) => {
    let cnt = 0
    for (let i = 2; cnt < 2 && i * i <= num; ++i) {
        while (num % i == 0) {
            num /= i
            ++cnt
        }
    }
    if (num > 1)++cnt
    return cnt == 2 ? true : false
}

console.log(
    [4, 6, 9, 10, 14, 15, 21, 22, 25, 26, 33, 34, 35, 38, 39, 46, 49, 51, 55].filter(isSemiPrime)
        .length
)

Eesa 6 年前

这里是解决方案的Javascript版本,但它是55%:

function solution(N, P, Q) {

  function isPrime(num) {
    for(var i = 2; i < num; i++)
      if(num % i === 0) return false;
    return num > 1;
  }

  const min = Math.min(...P)
  const max = Math.max(...Q)
  const A = []
  for(let i=min;i<max;i++) {
      for(let j=min;j<max;j++) {
          if (isPrime(i) && isPrime(j)) {
              const prod = j * i
              if (prod > max) break
              if (A.includes(prod)) continue
              A.push(j * i)
          }
      }
  }

  const result = []
  for(let i=0;i<P.length;i++) {
      for(let j=P[i];j<=Q[i];j++) {
          result[i] = result[i] || 0
          if (A.includes(j)) {
              result[i]++
          }
      }
  }
  return result
}

John 5 年前

您的代码:

private static List<Integer> getPrimes(int max) {
    List<Integer> primes = new ArrayList<>(max / 2);

**    for (int i = 0; i < max; i++)
**        if (isPrime(i))
**            primes.add(i);

    return primes;
}

private static boolean isPrime(int val) {
    if (val <= 1)
        return false;
    if (val <= 3)
        return true;

**    for (int i = 2, sqrt = (int)Math.sqrt(val); i <= sqrt; i++)
**        if (val % i == 0)
**            return false;

    return true;
}

我已经标出了要注意的行。我会这样做:

private static List<Integer> getPrimes(int max) {
    List<Integer> primes = new ArrayList<>(max / 2);
    primes.add(2);

    for (int i = 3; i < max; i++)
        if (isPrime(i, primes))
            primes.add(i);

    return primes;
}

private static boolean isPrime(int val, List<Integer> primes) {
    int sqrtv = Math.sqrt(val);
    for (int i = 0; i < primes.length(); i++)
    {
        int prime = primes.get(i);
        if (val % primes.get(i) == 0)
        {
            return false;
        } else if (prime > sqrtv) {
            return true;
        }
    }

    return true;
}

这是基于以下事实:

对iPrime的唯一调用来自getPrimes。GetPrime将始终按升序调用val。
在确定素数时,用非素数划分是没有意义的。如果我们已经知道一个数字“a”不能被2整除,那么为什么还要费心把它除以4、6、8或10呢?如果我们知道它不能被3整除,那么它就不能被9整除。。。因此,所有的非素数检查都是通过使用先前计算的素数来过滤的,只是为了执行检查。

Kiriakos 5 年前

这是我的100%个C++。我用的是前缀。时间复杂度O(N*log(log(N))+M)。

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

vector<int> solution(int N, vector<int> &P, vector<int> &Q)
{
    vector<bool> sieve(N, true);
    vector<int> ret;
    sieve[0] = sieve[1] = false;
    int i = 2;

    while (i * i <= N)
    {
        if (sieve[i])
        {
            int k = i * i;
            while (k <= N)
            {
                sieve[k] = false;
                k += i;
            }
        }
        i++;
    }

    vector<int> prefixSum(N + 1, 0);
    
    for (int i = 2; i <= sqrt(N); i++)
        if (sieve[i])
            for (int j = i; j <= N; j++)
            {
                if (j * i > N)
                    break;

                if (sieve[j])
                    prefixSum[j * i]++;
            }

    int carry;
    for (unsigned int i = 5; i < prefixSum.size(); i++)
    {
        carry = prefixSum[i - 1];
        prefixSum[i] += carry;
    }

    for (unsigned int i = 0; i < P.size(); i++)
        ret.push_back(prefixSum[Q[i]] - prefixSum[P[i] - 1]);

    return ret;
}

nialloc 5 年前

100%的溶液分解。 https://app.codility.com/demo/results/trainingGVNHKU-MA5/

首先,使用埃拉托什尼筛来确定什么是prime。

def get_sieve(n):
    # Use the sieve or Eratosthenes to produce an array of primes 
    # where factor[n] == 0 indicates a prime number
    factors = [0] * (n+1)
    i=2
    i2 = i*i
    while (i2 <= n):
        if not factors[i]:
            k = i2
            while k <= n:
                if not factors[k]:
                    factors[k] = i
                k += i
        i += 1
        i2 = i*i
    return factors

接下来,确定该数字是否为半素数。如果它的两个因子都是素数,那么它就是半素数。

def is_semi_prime(n, factors):
    if factors[n]: # Check its not a prime
        for r in range(int(n**.5)+1, 1, -1):
            if not n%r:
                d = n//r
                return (not factors[d]) and (not factors[r])
    return False

然后扫描N个数的范围,计算递增半素数的斜率。只需测量一个切片内的斜率,就可以看到该切片中出现了多少个半素数。

def solution(N, P, Q):
    # produce a slope of increasing semi primes
    factors = get_sieve(N)
    slope = [0] * (N+1)
    for i in range(1, N+1):
        slope[i] = slope[i-1] + is_semi_prime(i, factors) # Auto casting!! :-)
    # Optimus Prime!
    # print(list(enumerate(slope)))
    return [slope[Q[j]] - slope[P[j]-1] for j in range(len(P))]

https://github.com/niall-oc/things/blob/master/codility/count_semiprimes.py 更多关于 https://github.com/niall-oc/things/blob/master/codility/

Graham 5 年前

我采取了稍微不同的方法。该线程中的其他有效解决方案构建了一个规则的Eratosthenes(F)筛,其中记录了槽中最小的素数因子,因此半素数是那些F[x]>0和F[x//F[x]]==0,即除以最小的素数因子得到另一个素数。

那么半素数就是那些正好有2个素数因子的位置。

之后,我构建了一个半素数前缀计数,用它在固定时间内回答查询。

def solution(N, P, Q):
    num_factors = [0] * (N+1)
    for i in range(2, N+1):
        if num_factors[i] == 0:
            # Count visits to multiples of i by adding i each time
            add_visit = i+i
            while add_visit < N+1:
                num_factors[add_visit] += 1
                add_visit += i
            # But squares of prime count as 2 factors, cubes count as 3 etc,
            # so also run visits for multiples of the squares, cubes, etc. 
            power_prime = i*i
            while power_prime < N+1:
                visit = power_prime
                while visit < N+1:
                    num_factors[visit] += 1
                    visit += power_prime
                power_prime *= i
    semiprime_prefix_count = [0] * (N+1)
    for i in range(1, N+1):
        semiprime_prefix_count[i] = semiprime_prefix_count[i-1]
        if num_factors[i] == 2:
            semiprime_prefix_count[i] += 1
    results = []
    for p, q in zip(P, Q):
        results.append(semiprime_prefix_count[q] - semiprime_prefix_count[p-1])
    #print(list(zip(range(N+1),num_factors)))
    #print(list(zip(range(N+1),semiprime_prefix_count)))
    return results