897 - Anagrammatic Primes

All about problems in Volume 8. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

abc
New poster
Posts: 15
Joined: Sun Dec 15, 2002 2:51 pm

897 - Anagrammatic Primes

Post by abc » Fri Jul 16, 2004 10:01 pm

What changed after rejudge? Is there any anaglemtic primes after 991? What are the traps?

HidWalker
New poster
Posts: 3
Joined: Wed May 05, 2004 9:04 am

Post by HidWalker » Fri Jul 16, 2004 11:35 pm

I Found some I/O, may be you can try...

Input:
1
2
3
4
5
6
7
8
9

Output:
2
3
5
5
7
7
0
0
0


Hope it helps :)

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Fri Jul 16, 2004 11:53 pm

I also get the same input, though I also get WA. I find that there is 22 of these primes.. is there more?

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. » Sat Jul 17, 2004 7:37 pm

Yes, my accepted program also found 22 anaglemtic prime.
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Sun Jul 18, 2004 5:15 am

I corrected my error.. I had a typo in one part.. whoops.. =)

L I M O N
Learning poster
Posts: 58
Joined: Wed Dec 31, 2003 8:43 am
Location: Dhaka, Bangladesh
Contact:

Re: 897 WA

Post by L I M O N » Mon Jul 19, 2004 10:46 am

abc wrote:What changed after rejudge? Is there any anaglemtic primes after 991? What are the traps?
no , there is no ana. prime after 991. There are only 22 ana. primes.
i think there is no trips in this problem. Just do what's the problem say.
how do you consider the case "You must find the first anagrammatic prime which is larger than n and less than the next power of 10 greater than n." ???

L I M O N
Last edited by L I M O N on Tue Jul 20, 2004 9:32 am, edited 1 time in total.

InOutMoTo
New poster
Posts: 18
Joined: Sun Aug 10, 2003 12:47 pm

Post by InOutMoTo » Tue Jul 20, 2004 9:02 am

We can know that from n > 10, if n is a ana.prime ,
the digits of n can only contain 1, 3, 7, 9.
(since even number & 5 obviously cant be ana.prime)

But, does anyone know why numbers bigger than 1000
with digits of 1, 3, 7, 9 can't be ana. prime?
(or just by this program result?)

I try to find it , but failed.

L I M O N
Learning poster
Posts: 58
Joined: Wed Dec 31, 2003 8:43 am
Location: Dhaka, Bangladesh
Contact:

Post by L I M O N » Tue Jul 20, 2004 9:29 am

InOutMoTo wrote:We can know that from n > 10, if n is a ana.prime ,
the digits of n can only contain 1, 3, 7, 9.
(since even number & 5 obviously cant be ana.prime)
But, does anyone know why numbers bigger than 1000
with digits of 1, 3, 7, 9 can't be ana. prime?
(or just by this program result?)
9 isn't a prime number.
how do you sure that there is no ana. prime after 1000 ???

L I M O N

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Tue Jul 20, 2004 10:05 am

Well there ARE bigger anagrammatic primes!!!

http://www.research.att.com/cgi-bin/acc ... num=004023

From this we know that 1111111111111111111 is also an anagrammatic prime @_@
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

InOutMoTo
New poster
Posts: 18
Joined: Sun Aug 10, 2003 12:47 pm

Post by InOutMoTo » Wed Jul 21, 2004 10:34 am

TO LIMON : I didn't say 9 is ana.prime. :o I say : "If n is a ana.prime ,
the digits of n can only contain 1, 3, 7, 9. "

TO Observer: Thanks for your data :lol:

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Thu Jul 22, 2004 12:23 am

Observer: I've meant to say, "in the range", though I left it out.. thanks for the interesting data!

L I M O N
Learning poster
Posts: 58
Joined: Wed Dec 31, 2003 8:43 am
Location: Dhaka, Bangladesh
Contact:

Post by L I M O N » Thu Jul 22, 2004 5:33 am

InOutMoTo wrote:TO LIMON : I didn't say 9 is ana.prime. :o I say : "If n is a ana.prime ,
the digits of n can only contain 1, 3, 7, 9. "

:lol:
Sorry InOutMoTo,
i really misunderstand.
L I M O N

User avatar
Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am

Post by Kallol » Sat Jul 08, 2006 1:03 pm

only 22 anagramatic primes IN THE RANGE ...

they are :
0->10
----------
1. 2
2. 3
3. 5
4. 7

10->100
-----------
5. 11
6. 13
7. 17
8. 31
9. 37
10. 71
11. 73
12. 79
13. 97

100->1000
---------------
14. 113
15. 131
16. 199
17. 311
18. 337
19. 373
20. 733
21. 919
22. 991

if input is greater than 991 , ans would be 0.

precalculation makes it an easy problem .
Syed Ishtiaque Ahmed Kallol
CSE,BUET
Bangladesh

clare
New poster
Posts: 7
Joined: Wed Aug 23, 2006 5:19 pm

897 WA Anagrammatic Primes

Post by clare » Wed Aug 23, 2006 5:25 pm

Hello everyone!
I am getting WA with this code :cry: Could someone plz give me a hint.
From the previous post I understood that anagrammatic primes are only in the range from 1 to 1000. Is that right? :o

However, here is my code:

#include<iostream>
#include<string>
#include<algorithm>
#include<cmath>
#include<stdio.h>

using namespace std;

bool is_prime(long long int result)
{
bool prime = true;
for(long long int i = 2;prime and i*i<=result; i++)
{
if(result%i==0)
prime = false;
}
return prime;
}

string to_string(long long int n)
{
string result="";
while(n/10!=0)
{
result+=(n%10) + '0';
n/=10;
}
result+=(n%10)+'0';
return result;
}

string reverse(string num)
{
string result="";
for(int i=num.size()-1; i>=0; i--)
result+=num;
return result;
}

long long int to_int(string num)
{
long long int result = 0;
int times = 1;
for(int i = num.size()-1; i>=0; i--)
{
result+=(num-'0')*times;
times*=10;
}
return result;
}

bool check(string num)
{
bool result = true ;
long long int number = to_int(num);
result = is_prime(number);
for(int i = 0; i<num.size(); i++)
{
for(int j=1; result and j<num.size(); j++)
{
swap(num[j-1], num[j]);
number = to_int(num);
result = is_prime(number);
if(result==false)
goto stop;

}
}
stop:
return result;
}

int main()
{
long long int array[50];
array[0]=2; array[1]=3; array[2]=5; array[3]=7;
int a =4;
for(long long int i = 10; i<=1000; i++)
{
string string_num = to_string(i);
bool ok = check(string_num);
if(ok)
{
array[a]=i;
a++;
}
}
long long number;
while(cin>>number and number !=0)
{
if(number>1000)
cout<<0<<endl;
string broj = to_string(number);
double len = broj.size();
long long int power = static_cast<long long int>(pow(10, len));
bool go = true;
for(int g=0; go and g<a; g++)
{
if(array[g]>number and array[g]<power)
{
cout<<array[g]<<endl;
go = false;
}
}
}
}

Thanx! :wink:

smile2ka10
New poster
Posts: 13
Joined: Wed Oct 26, 2005 10:14 pm
Location: Iran
Contact:

Post by smile2ka10 » Sun Aug 27, 2006 10:03 pm

Don't you think that 1 is a power of 10?! ;)

Post Reply

Return to “Volume 8 (800-899)”