题目187：半质数

欧拉计划

Semiprimes

A composite is a number containing at least two prime factors. For example, 15 = 3 × 5; 9 = 3 × 3; 12 = 2 × 2 × 3.

There are ten composites below thirty containing precisely two, not necessarily distinct, prime factors: 4, 6, 9, 10, 14, 15, 21, 22, 25, 26.

How many composite integers, n < 10⁸, have precisely two, not necessarily distinct, prime factors?

题目：

一个合数是至少两个质数因子的乘积，比如 15 = 3 × 5； 9 = 3 × 3； 12 = 2 × 2 × 3。

30 以内的数中有 10 个合数，它们有且仅有两个质数因子，这两个因子可能相同：4, 6, 9, 10, 14, 15, 21, 22, 25, 26。

请问，对于 n < 10⁸，有多少个数字只有两个质数因子？这两个质数因子可能相同。

jerryxjr1220

import numpy as np 
from numba import jit
@jit
def solve(n):
        sieve=np.ones(n+1,dtype=bool)
        for i in range(2, int((n+1)**0.5+1)):
                if sieve[i]:
                        sieve[i*i::i]=False
        plist = np.nonzero(sieve)[0][2:]
        count = 0
        for i in range(len(plist)):
                j = i
                while plist[i]*plist[j] < n:
                        count += 1
                        j += 1
        return count
print(solve(10**8))

17427258
[Finished in 4.5s]

永恒的蓝色梦想

C++ 322ms

#include<iostream>
#include<vector>
#include<cstring>
using namespace std;



template<size_t size, typename T>
void euler_sieve(bool (&is_prime)[size], vector<T>& primes) {
    T i, k;
    memset(is_prime, -1, size);
    is_prime[0] = is_prime[1] = 0;

    for (T i = 2; i < size; i++) {
        if (is_prime[i]) {
            primes.push_back(i);
        }

        for (T j : primes) {
            k = i * j;

            if (k >= size) {
                break;
            }

            is_prime[k] = false;

            if (!(i % j)) {
                break;
            }
        }
    }
}



int main() {
    ios::sync_with_stdio(false);
    
    constexpr unsigned int UPPER_BOUND = 100000000;
    static bool is_prime[UPPER_BOUND / 2];
    vector<unsigned int> primes;
    unsigned int i, j, result = 0;

    euler_sieve(is_prime, primes);


    for (i = 0; primes[i] * primes[i] < UPPER_BOUND; result += ++i);

    for (j = i; i < primes.size(); i++) {
        while (primes[i] * primes[j] >= UPPER_BOUND) {
            j--;
        }

        result += j;
        result++;
    }


    cout << result << endl;
    return 0;
}

guosl

优化来了。

/*
答案：17427258
耗时：1.41251
      0.643071 (8核)
*/
#include <iostream>
#include <vector>
#include <cmath>
#include <omp.h>
using namespace std;

const int N = 100000000;
const int M = int(sqrt(double(N)));

char cp[N];//cp[i]==1表示i为素数
bool pm[N];//pm[i]==true表示i为两个素数的乘积

int main(void)
{
  double t = omp_get_wtime();
  memset(cp, 1, sizeof(cp));
  int nCount = 0;
  bool bContinue = true;
#pragma omp parallel firstprivate(bContinue) shared(cp,pm) reduction(+:nCount)
  {
    for (int i = 2; i <= M; ++i)
    {
#pragma omp single copyprivate(bContinue)
      {
        bContinue = true;
        if (cp[i] == 0)
          bContinue = false;
      }
      if (!bContinue)
        continue;
#pragma omp for
      for (int j = i * i; j < N; j += i)
        cp[j] = 0;
    }
#pragma omp barrier
#pragma omp for schedule(dynamic)
    for (int i = 2; i <= M; ++i)
    {
      if (cp[i] == 0)
        continue;
      for (int j = i; i*j < N; ++j)
      {
        if (cp[j] == 1)
          pm[i*j] = true;
      }
    }
#pragma omp for
    for (int i = 4; i < N; ++i)
    {
      if (pm[i])
        ++nCount;
    }
  }
  t = omp_get_wtime() - t;
  cout << nCount << endl << t << endl;
  return 0;
}

代号-K

这题本质还是素数的求解，只是在求解的过程中加入了一些判断。

代号-K

永恒的蓝色梦想 发表于 2020-5-17 20:09
谢谢指导

有个优化过的帖子，不知道在哪里了，这个帖子不是优化的，重新写一个吧。