程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> poj 2635 The Embarrassed Cryptographer 篩素數+高精度除法

poj 2635 The Embarrassed Cryptographer 篩素數+高精度除法

編輯:C++入門知識

poj 2635 The Embarrassed Cryptographer 篩素數+高精度除法


題意:

給K(<10^100),L(<10^6),求K小於L的最小素因子並輸出,如果沒有則輸出GOOD。

分析:

枚舉小於L的素數用高精度除法判斷是否是因子,關鍵是怎麼高效篩素數,先給一種比較慢的篩法:

primes[max_prime_num],num=0;
memset(vis,0,sizeof(vis))
for(int i=2;i

 

這樣每個合數會被vis到的次數為該數的因子數,一個數的因子數比他的素因子數大很多,而n的素因子個數是logn的,效率很低。

 

一種比較快的方法:

primes[max_prime_num],num=0;
memset(vis,0,sizeof(vis));
for(int i=2;i這樣每個合數被vis到的次數僅為1,如2^4*3^6只在i==2^3*3^6,primes[j]==2時被vis到,2*3*5只在i==3*5,prime[j]==2被vis到,效率高於第一種方法。

 

代碼:

 

//poj 2635
//sep9
#include 
using namespace std;
int s[128],L,len;
int tmp[128];
char input[128];
const int maxL=1000024;
int vis[maxL+10];
int primes[maxL+10],num;

int divs(int q,int len)
{
	for(int i=0;i=0;--i){
			sum=pow10[cnt]*(input[i]-'0')+sum;
			if(cnt==2){
				s[t++]=sum;
				cnt=sum=0;
			}else
				++cnt;
			
		}
		if(sum!=0) s[t++]=sum;
		int i;
		for(i=0;i=L) puts("GOOD");
		else printf("BAD %d\n",primes[i]);	
	}
	return 0;	
}


 

 

 

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