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


          
		          		
	
          
	
          
		
			
          
			
          
		          		
		
			
          
				
					
	
          
		
          
			
          
				USACO 1.1.5 Prime Palindromes
			
          
 			Posted on 2007-06-01 21:28 ZelluX 閱讀(463) 評論(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;
          }
          

          
	
          
	


          
	    
    




          








          

				
			
          
		          		
	
          
	
          
		
			


		
	
          

          



    







          
        
	




主站蜘蛛池模板：
永川市|
中江县|
基隆市|
乌兰浩特市|
合作市|
邯郸县|
新绛县|
五寨县|
米脂县|
巴南区|
郎溪县|
公主岭市|
齐齐哈尔市|
房产|
乐山市|
凌海市|
大关县|
家居|
武宁县|
马龙县|
大名县|
龙口市|
楚雄市|
酒泉市|
元氏县|
五常市|
福建省|
磐安县|
海丰县|
都江堰市|
班戈县|
酉阳|
兴海县|
称多县|
兴仁县|
靖西县|
齐齐哈尔市|
固安县|
平安县|
山东省|
高阳县|