Snowdream

posts - 403, comments - 310, trackbacks - 0, articles - 7

USACO 1.1.5 Prime Palindromes

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

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

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

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;

}

新用戶注冊刷新評論列表


只有注冊用戶登錄后才能發(fā)表評論。




網(wǎng)站導航: 博客園 IT新聞 Chat2DB C++博客博問管理
相關文章: 函數(shù)式編程另類指南[zz] URAL 1011 Sorting Networks URAL 題解 - wiki 《編程之美》上的一道題目的討論求n個32位無符號整數(shù)中異或后值最大的兩個數(shù) SICP 習題記錄 (1) 正則表達式的復雜度 Minesweeper is NP-complete Tom Duff on Duff's Device

Snowdream

USACO 1.1.5 Prime Palindromes

日歷

常用鏈接

留言簿(21)

隨筆分類(390)

隨筆檔案(389)

文章檔案(7)

相冊

15ers

友情鏈接

收藏夾

搜索

積分與排名

最新隨筆

最新評論

閱讀排行榜

評論排行榜