程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 獲取小於N的素數 優化篩選法的C++實現

獲取小於N的素數 優化篩選法的C++實現

編輯:C++入門知識

獲取小於N的素數 優化篩選法的C++實現


孿生素數(間隔為2的相鄰素數)的相關定理與推論

P1: 當 N 不小於 6 且 N-1 和 N+1 為 孿生素數, 則 N 一定是 6的倍數

T1:當 N 不小於 1 且 N=6x-1 或 N=6x+1 不是素數, 那麼 N 一定不是 2和 3的倍數

P2:當N 不小於 5 時,若 N 為素數,那麼N mod 6 =1或N mod 6 = 5

T2: 一個大於5的數有且只有整除6余數是 1 或者 5 才有可能是素數

一個數 整除6 的余數 可能是 1,2,3,4,5 但是 余數 為2,3,4的情況下 肯定是合數

具體代碼如下

/*
 ***************************************************************
 *    NAME: select_prime.cpp
 *    DESC:
 *  AUTHOR: Liu Dongguo([email protected])
 * VERSION: 1.0
 *  CREATE: 2015-04-09 13:59:45
 *  LUTIME: 2015-04-10 01:53:40
 *
 * Copyright (c) 2007 - 2015 Abodu.com,Inc. All Rights Reserved
 *
 ***************************************************************
 */

#include 
#include 
#include 

char* GetPrimesLessN(int nSize) //nSize是上限值
{
    int fLen= nSize;
    char* flag=new char[fLen];//
    memset(flag,'y',fLen);
    flag[0]=flag[1]='s'; //排除0和1
    for(int i=2;i*i

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved