欧拉计划 发表于 2016-10-5 15:50:21

题目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 < 108, 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 < 108，有多少个数字只有两个质数因子？这两个质数因子可能相同。

jerryxjr1220 发表于 2017-9-22 11:25:03

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:
                        sieve=False
      plist = np.nonzero(sieve)
      count = 0
      for i in range(len(plist)):
                j = i
                while plist*plist < n:
                        count += 1
                        j += 1
      return count
print(solve(10**8))
17427258

永恒的蓝色梦想 发表于 2020-4-21 18:43:43

本帖最后由 永恒的蓝色梦想 于 2021-2-20 20:38 编辑

C++ 322ms#include<iostream>
#include<vector>
#include<cstring>
using namespace std;



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

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

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

            if (k >= size) {
                break;
            }

            is_prime = false;

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



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

    euler_sieve(is_prime, primes);


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

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

      result += j;
      result++;
    }


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

guosl 发表于 2020-5-17 14:49:37

优化来了。/*
答案：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;//cp==1表示i为素数
bool pm;//pm==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 == 0)
          bContinue = false;
      }
      if (!bContinue)
      continue;
#pragma omp for
      for (int j = i * i; j < N; j += i)
      cp = 0;
    }
#pragma omp barrier
#pragma omp for schedule(dynamic)
    for (int i = 2; i <= M; ++i)
    {
      if (cp == 0)
      continue;
      for (int j = i; i*j < N; ++j)
      {
      if (cp == 1)
          pm = true;
      }
    }
#pragma omp for
    for (int i = 4; i < N; ++i)
    {
      if (pm)
      ++nCount;
    }
}
t = omp_get_wtime() - t;
cout << nCount << endl << t << endl;
return 0;
}

代号-K 发表于 2020-5-17 20:07:44

本帖最后由 代号-K 于 2020-5-17 20:10 编辑

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

代号-K 发表于 2020-5-17 20:11:02

本帖最后由 代号-K 于 2020-5-17 20:13 编辑

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

有个优化过的帖子，不知道在哪里了，这个帖子不是优化的，重新写一个吧。
页: [1]
查看完整版本: 题目187：半质数