求一千萬以內由兩個素數相乘的數，並按從小到大排列，如：6=23，10=25。有什麼比較好的思路嗎？

01-04

要求：最好能用標準c/c++實現，性能當然越快越好，內存要求越小越好（最多4g內存）。

篩素數過程就是標記素數的倍數，所以對於整數n，你可以順便保存下其最小質因子發factor[n]

然後掃描1000w以內的數，對於整數n,若factor[n] = n，則n是素數。否則檢查n / factor[n]是否是素數，是就說明n是兩個素數相乘的結果。

篩選素數時空複雜度是O(n)，也就是以上演算法的時空複雜度。

素數篩法改一下就可以了

用線性篩寫了一個，時空複雜度均為 $O(N)$

#include "bits/stdc++.h"


using namespace std;
const int maxn = 10000000+10;

bitset&isPrime;

int smallestFactor[maxn],primes[maxn/10],primeCount;
vector& sieve(int n){

	isPrime.set();

	primeCount = 0;

	isPrime[0] = isPrime[1] = 0;

	for(int i = 2;i&<=n;i++){
		if(isPrime[i]){
			primes[primeCount++] = i;
			smallestFactor[i] = i;
		}
		for(int j = 0;j&ans;

	for(int i = 2;i&<=n;i++){
		if(isPrime[i/smallestFactor[i]]){
			ans.push_back(i);
		}
	}
	return ans;
}

int main(){
	vector& v = sieve(10000000);

	for(auto i:v)cout&<&

Select[Range[10000000], PrimeOmega[#] == 2 ]



 
1. 埃氏篩法。這一步複雜度 。
2. 乘。設一千萬內素數個數為n，那麼由於任意兩個質數都是互質的，所以乘積都是不同的，所求的數的數目應該是。這一步用到兩重循環計算乘積，複雜度為。
3. 排序嘛，快排，複雜度。
總的複雜度  ，常數因子可能很大。

 
是要求兩個不同素數么，還是可以相同，比如4=2x2
不管是什麼要求，我第一反應就是篩，弄個bitmap，類似篩素數，但是碰到素數略過，碰到兩個素數相乘的，就把它所有倍數篩掉，因為n=pq這種形式的倍數可能是三個素數以上相乘的

A001358 - OEIS
1. 生成500萬以內的素數表。
2. 從以上素數表中取兩個數，乘積放入 vector ，注意不重不漏。

 
3. 對 vector 排序。
  int max = 1e7;

  std::vector& primes = getPrimes(max/2);

  printf("%zd

", primes.size());

  std::vector& biprimes;

  for (int i = 0; i &< primes.size()  primes[i] &< sqrt(max); ++i) {
    for (int j = i; j &< primes.size()  primes[i] * primes[j] &< max; ++j) {
      biprimes.push_back(primes[i] * primes[j]);
    }
  }
  printf("%zd
", biprimes.size());
  // 排序略

我算出來的結果有 1904324 個數。

一個for循環，從1到1000萬，
判斷i是不是有兩個素因數，如果是，就保存起來

 
這樣的結果就不需要再排序了

Mathematica:
n=1*^7;l=Prime@Range@PrimePi@n;

Union@@Table[p TakeWhile[l,p#&
~ 5s

不懂c，大概說下思路。
每十萬分個組，利用多線程將所有分組裡的素數求出來，並存入類似於字典的數據結構，key就是順序序號。
然後遍歷的時候就可依次輸出了。
速度還可以，就是要存儲所有素數。

  推薦閱讀：


※在學習數據結構與演算法的時候，一旦出現遞歸就很難理解。請問對於遞歸有沒有什麼好的理解方法？
※世界上最複雜的程序演算法有哪些？是如何設計和用來做什麼的？
※C語言「尋找100000以內的所有素數？」為什麼這麼寫？
※Dijkstra演算法能否用於有環圖？
TAG:演算法 | 編程 | 編程學習 | 演算法設計 | 演算法與數據結構 |

求一千萬以內由兩個素數相乘的數，並按從小到大排列，如：6=2*3，10=2*5。有什麼比較好的思路嗎？

求一千萬以內由兩個素數相乘的數，並按從小到大排列，如：6=23，10=25。有什麼比較好的思路嗎？