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

USACO 1.1.5 Superprime Rib

Posted on 2007-06-01 22:32 ZelluX 阅读(244) 评论(0)  编辑  收藏 所属分类: Algorithm

开始的方法太慢了,Superprime要从一位数开始生成,逐渐增加位数。


/*
PROG: sprime
ID: 06301031
LANG: C++
*/


#include 
<iostream>
#include 
<fstream>
#include 
<cmath>
#include 
<vector>
#include 
<algorithm>

using namespace std;

bool isPrime(long n) {
    
if (n == 1{
        
return false;
    }

    
for (int i = 2; i <= sqrt(n); i++{
        
if (n % i == 0{
            
return false;
        }

    }

    
return true;
}


int main() {
    ifstream fin(
"sprime.in");
    ofstream fout(
"sprime.out");
    
int n;
    fin 
>> n;
    
long i, j;
    
long base = 1;
    vector
<long> prev, now;
    vector
<long>::iterator iter;
    prev.push_back(
0);
    
for (i = 1; i <= n; i++{
        
for (j = 1; j <= 9; j++{

            
for (iter = prev.begin(); iter != prev.end(); iter++{
                
long number = *iter * 10 + j;
                
if (isPrime(number)) {
                    now.push_back(number);
                }

            }

        }

        prev 
= now;
        now.clear();
        
base *= 10;
    }


    sort(prev.begin(), prev.end());
    
for (iter = prev.begin(); iter != prev.end(); iter++{
        fout 
<< *iter << endl;
    }

}

只有注册用户登录后才能发表评论。


网站导航: