posts - 403, comments - 310, trackbacks - 0, articles - 7
  BlogJava :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

USACO 1.1.5 Prime Palindromes

Posted on 2007-06-01 21:28 ZelluX 阅读(462) 评论(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;
}

只有注册用户登录后才能发表评论。
网站导航: