## 11353 - A Different Kind of Sorting

Moderator: Board moderators

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

### solved it

OK, seems I had almost done it (solved it) by the
time I have made my previous post. So you may ignore it,
as I have it ACC now with a runtime of about 1/2 second (0.460 secs).

Still, I make one assumption up-front which I don't like
very much, although everyone can check up-front
that this assumption is true (or can also prove it quite
easily in a mathematical way).

The assumption is that each number from 1 to 2,000,000
has at most 20 prime factors and actually only two numbers
have exactly 20 prime factors: 1048576 and 1572864.

Good luck to everyone.

Nursoltan_h
New poster
Posts: 9
Joined: Sat Jun 12, 2010 2:11 pm
Location: Ulaanbaatar, Mongolia
Contact:

### Re: 11353 - A different kind of Sorting

My code runs in 11.094sec

Code: Select all

``````/*
NAME : Nursoltan
PROB :
LANG : C++
*/
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <fstream>
#include <iostream>
#include <map>
#include <set>
#include <stack>
#include <utility>
#include <queue>

using namespace std;

#define MAX 2000000
#define INF INT_MAX
#define eps (1e-9)

#define FOR(_i,_k,_n) for(int (_i)=(_k); (_i)<(_n); (_i)++)
#define FORR(_i,_k,_n) for(int (_i)=(_k); (_i)>=(_n); (_i)--)
#define CLR(_x) memset((_x),0,sizeof(_x))
#define SQR(_x) ((_x)*(_x))
#define all(_x) _x.begin(),_x.end()

#define vc vector<int>
#define pb push_back
#define mp make_pair
#define iss istringstream
#define oss ostringstream
#define px first
#define py second

typedef long long ll;
typedef pair <int,int> point;
int ABS(int _x){ return _x>0?_x:-_x; }

bool sieve[MAX+1];
int a[MAX+1],N,n=1;
set<int> st;
set<int>::iterator it;

int main()
{
clock_t start = clock();
a=1;
for(int i=2; i<=MAX; i++){
if(!sieve[i]){ a[n++]=i; st.insert(i); }
for(int j=2*i; j<=MAX; j+=i) sieve[j]=1;
}
N=n;
for(int i=1; i<20&&N<MAX; i++){
for(int j=1; j<n; j++){
for(it=st[i-1].begin(); it!=st[i-1].end()&&int(*it)*a[j]<=MAX; it++){
if(st[i].count(int(*it)*a[j])) break;
st[i].insert(int(*it)*a[j]);
}
}
for(it=st[i].begin(); it!=st[i].end()&&N<MAX; it++) a[N++]=int(*it);
}

clock_t end = clock();
cout<<N<<" "<<double(end-start)/CLOCKS_PER_SEC;

while(1){
int f;
cin>>f; cout<<a[f-1]<<endl;
}

system("pause");
return 0;
}
``````
How can i optimize my code???

arifcsecu
Learning poster
Posts: 64
Joined: Fri Sep 25, 2009 11:29 am
Location: Chittagong,University of chittagong
Contact:

### Re: 11353 - A different kind of Sorting

try to use sieve method..
in the flying of sieve method , just calculate the factor of all number
then use qsort() / sort()..
Try to catch fish rather than asking for some fishes.