posts - 403, comments - 310, trackbacks - 0, articles - 7
          
	
 
BlogJava ::
首頁 ::
新隨筆 ::
聯系 ::
聚合
 ::
管理


          
		          		
	
          
	
          
		
			
          
			
          
		          		
		
			
          
				
					
	
          
		
          
			
          
				USACO 1.1.5 Prime Palindromes
			
          
 			Posted on 2007-06-01 21:28 ZelluX 閱讀(465) 評論(0)  編輯  收藏  所屬分類: Algorithm 
			
			


		
          
		
          Packing Rectangles先cheat了，下星期再回來做。

          先用篩法做了一張hash表，記錄是否為素數，然后找各個素數判斷是否為回文數，超內存了。。。
          于是改為生成回文數后判斷是否為素數，過了。
          貌似現在寫這種程序的速度比高中快不少了，到底是什么進步了呢？
          

          /*
          PROG: pprime
          ID: 060301031
          LANG: C++
          */

          #include           <iostream>
          #include           <fstream>
          #include           <bitset>
          #include           <cmath>

          using namespace std;

          bool isPrime(const long num) {
                        int i;
                        for (i = 2; i <= sqrt(num); i++) {
                            if (num % i == 0) {
                                return false;
                  }
              }
                        return true;
          }

          int main() {
              ifstream fin(          "pprime.in");
              ofstream fout(          "pprime.out");
                        long from, to;
                        long i = 0, j;
              fin           >> from >> to;
              
                        long beginNum = 1;
                        while (true) {
                            int number;
                  i          ++;  // i indicates the digits of palindromes to be generated
                  for (j = beginNum; j < beginNum * 10; j++) {
                                long num1 = j, num2 = 0, temp = j;
                                if (i % 2 == 1) {
                          temp           /= 10;
                      }
                                while (temp > 0) {
                          num1           *= 10;
                          num2           = num2 * 10 + (temp % 10);
                          temp           /= 10;
                      }
                      number           = num1 + num2;
                                if (number > to) {
                                    break;
                      }
                                if (number < from) {
                                    continue;
                      }
                                if (isPrime(number)) {
                          fout           << number << endl;
                      }
                  }
                            if (number > to) {
                                break;
                  }
                            if (i % 2 == 0) {
                      beginNum           *= 10;
                  }
              }
                        return 0;
          }
          

          
	
          
	


          
	    
    




          








          

				
			
          
		          		
	
          
	
          
		
			


		
	
          

          



    







          
        
	




主站蜘蛛池模板：
焉耆|
锡林浩特市|
吴江市|
高台县|
河东区|
庄浪县|
阜新市|
鸡泽县|
南召县|
迁西县|
白山市|
广昌县|
沈丘县|
仙游县|
江源县|
阿拉善盟|
如东县|
赣州市|
临泉县|
高安市|
甘南县|
广西|
合江县|
克什克腾旗|
搜索|
拉萨市|
乐山市|
阳高县|
宜宾县|
中超|
通山县|
玛曲县|
谷城县|
会泽县|
翼城县|
永康市|
巴东县|
岑溪市|
崇信县|
庆城县|
银川市|