You are not logged in. Please login at www.codechef.com to post your questions!

×

codevita,concatenating, primes,concatinating primes

Guys i really need help on this one. Codevita 2k17 just got finished so as u guys know TCS don.t provide solution of their Questions. Here is the question:- If you like numbers, you may have been fascinated by prime numbers. Sometimes we obtain by concatenating two primes. For example, concatenating 2 and 3, we obtain the prime 23. The aim is to find all such distinct "concatenated primes" that could be obtained by concatenating primes ≤ a given integer N. Input Format:

Integer N Output Format:

M, the number of distinct primes that could be obtained by concatenating two primes ≤ N Constraints:

N ≤ 70

Example 1

Input 10

Output 4

Explanations The primes ≤ 10 are 2, 3, 5, 7. These can be used to form the following concatenated numbers: 22, 23, 25, 27, 32, 33, 35, 37, 52, 53, 55, 57, 72, 73, 75, 77. Of these, there are four primes: 23 37 53 and 73. Hence the output is 4.

Example 2

Input 20

Output 17

Explanation The prime numbers up to 20 are 2 3 5 7 11 13 17 and 19.

Concatenating these two at a time in all possible ways, we get the following numbers:

22 23 25 27 211 213 217 219 32 33 35 37 311 313 317 319 52 53 55 57 511 513 517 519 72 73 75 77 711 713 717 719 112 113 115 117 1111 1113 1117 1119 132 133 135 137 1311 1313 1317 1319 172 173 175 177 1711 1713 1717 1719 192 193 195 197 1911 1913 1917 1919

We have the following 17 primes numbers in this list: 23 37 53 73 113 137 173 193 197 211 311 313 317 719 1117 1319 1913 Hence the output would be 17.

I would really appreciate the solution of this question or if someone pointout error in mine code. Here is mine code:
import java.util.Scanner;
class symbol {
    public static void main(String[] args) {
        Scanner inp = new Scanner(System.in);
        Integer n = inp.nextInt();
        if(n<3){
            System.out.println("0");
            System.exit(0);
        }
        int flag = -1;
        int len;
        int count=0,count2=0;
        String primes[] = {"2", "3", "5", "7", "11", "13", "17", "19", "23", "29", "31", "37", "41", "43", "47", "53", "59", "61", "67"};

        for(int i=0;i<primes.length;++i){
            if(n>=Integer.parseInt(primes[i]))
                flag=i;
            else if(n<Integer.parseInt(primes[i]))
                break;
        }
//        System.out.println(primes[flag]+" "+flag);
        len = (flag+1)*(flag+1);
        String arr[]= new String[len];
        for(int i=0;i<=flag;++i){
            for(int j=0;j<=flag;++j) {
                arr[count2] = primes[i] + primes[j];
                //System.out.print(arr[count2]+" ");
                count2++;
            }
            //System.out.println();
            //System.out.print("jj"+arr[i]);
        }
//        for(int i=0;i<arr.length;++i){
//            System.out.print(arr[i]+" ");
//        }
        //       System.out.println(arr.length+"lenth"+arr[14]);
        int lol=Integer.parseInt(arr[arr.length - 1]);
        boolean prime[] = new boolean[lol+1];
//        System.out.println(prime.length);
        for(int p = 2; p*p <=lol; p++)
        {
            if(prime[p] == false)
            {
                for(int i = p*2; i <= lol; i += p)
                    prime[i] = true;
            }
        }

//        for(int i = 2; i <prime.length; i++)
//        {
//            if(prime[i] == false){
//                System.out.print(i + " ");
//
//            }
//        }
//        System.out.println("prime");
//        for(int i=0;i<arr.length;++i)
//            System.out.print(arr[i]+" ");
        for(int i=0;i<arr.length;++i)
            for(int j=2;j<prime.length;++j) {
                if (prime[j] == false) {
                    if (Integer.parseInt(arr[i])==j) {
                       // System.out.print(arr[i] + " ");
                        count++;
                    }
                }
            }
        System.out.println(count);
    }
}

Thanks in advance.

asked 29 Jul '17, 14:53

jj_no1's gravatar image

0★jj_no1
12
accept rate: 0%

edited 29 Jul '17, 14:56


you both are double counting..

for example consider: 317

you're creating 317 twice using {31,7} and {7,31}. like this, you are counting many primes twice. Just use a map to check if you already built a prime or not before incrementing the count variable.

link

answered 29 Jul '17, 19:11

swetankmodi's gravatar image

6★swetankmodi ♦♦
6008
accept rate: 15%

Don't know about @stephen26 's code but there is no doubling in mine code...to verify uncomment "// System.out.print(arr[i] + " ");" from last, u'll see the concatenated primes.

(30 Jul '17, 03:15) jj_no10★

I dont know the answer either .. here's my code

import java.util.*;


class prime
 {
public static boolean isPrime(int n) {
for (int f = 2; f <=Math.sqrt(n); f++) {
    if (isFactor(f, n))
        return false;
}
return true;
}
private static boolean isFactor(int factor, int number) {
return number % factor == 0;
}
public static void main(String args[])
  {
  int[] prime = new int[70];
  int n,k=0,count=0;
    Scanner sc = new Scanner(System.in);
    n = sc.nextInt();
 for (int i = 2; i<=n; i++)
 {
   if (isPrime(i))
     {
     prime[k] = i;
     k++;
     //System.out.println(i);
     }

     }
     for(int i=0; i<k; i++)
     {
     for(int j=0; j<k; j++)
       {
      String s = Integer.toString(prime[i]);
      String t = Integer.toString(prime[j]);
      String u = s+t;
      //System.out.println(u);
      if(isPrime(Integer.parseInt(u)))
            count++;
       }

     }
        System.out.print(count);
     }

     }
link

answered 29 Jul '17, 18:00

stephen26's gravatar image

0★stephen26
1
accept rate: 0%

I try this program in python. My program is b=[] e=[] f=[] x=int(input('Enter the last number:')) for i in range(2,x+1): a=0 for j in range(2,x+1): if i%j==0: a+=1 if j==1 or j==i: a-=1 if a==0: b.append(i) print(b,'is prime number') for i in range(0,len(b)): for j in range(0,len(b)): if len(str(b[i]))==1 and len(str(b[j]))==1: d=(b[i]10)+b[j] e.append(d) elif len(str(b[i]))==1 and len(str(b[j]))>1: d=(b[i]100)+b[j] e.append(d) elif len(str(b[i]))>1 and len(str(b[j]))==1: d=(b[i]10)+b[j] e.append(d) elif len(str(b[i]))>1 and len(str(b[j]))>1: d=(b[i]100)+b[j] e.append(d) for i in range(0,len(e)): c=0 for j in range(2,100): if e[i]%j==0: c+=1 if j==e[i]: c-=1 if c==0: f.append(e[i]) print(len(f))

link

answered 30 Jul '17, 11:38

dinesh_kumar56's gravatar image

0★dinesh_kumar56
1
accept rate: 0%

I try this program in python. My program is
b=[]
e=[]
f=[]
x=int(input('Enter the last number:'))
for i in range(2,x+1):
a=0
for j in range(2,x+1):
if i%j==0:
a+=1
if j==1 or j==i:
a-=1
if a==0:
b.append(i)
print(b,'is prime number')
for i in range(0,len(b)):
for j in range(0,len(b)):
if len(str(b[i]))==1 and len(str(b[j]))==1:
d=(b[i]10)+b[j]
e.append(d)
elif len(str(b[i]))==1 and len(str(b[j]))>1:
d=(b[i]
100)+b[j]
e.append(d)
elif len(str(b[i]))>1 and len(str(b[j]))==1:
d=(b[i]10)+b[j]
e.append(d)
elif len(str(b[i]))>1 and len(str(b[j]))>1:
d=(b[i]
100)+b[j]
e.append(d)
for i in range(0,len(e)):
c=0
for j in range(2,100):
if e[i]%j==0:
c+=1
if j==e[i]:
c-=1
if c==0:
f.append(e[i])
print(len(f))

link

answered 30 Jul '17, 11:42

dinesh_kumar56's gravatar image

0★dinesh_kumar56
1
accept rate: 0%

I SUBMITTED THIS CODE AND IT PASSSES THE PUBLIC TEST CASES BUT NOT PRIVATE TEST CASES PLEASE HELP IF I M WRONG ANYWHERE

include<stdio.h>

include<math.h>

int prime(int n) {

int i,count=0,k=0;

for(i=1;i<=n;i++) {

if(n%i==0)

{

count++;

if(count==1&&i==n/2)

{

return 1;

break;

}

if(count>2)

break;

}

}

if(count==2)

k=1;

else

k=0;

return k;

}

int bits(int w)

{

int c=0;

while(w>0)

{

w=w/10;

c++;

}

return c;

}

int main()

{

long int c=1,i,j=0,n,call=0,total=0,a[100000],recheck=0,count=0,connect=0,bitcheck=0;

scanf("%ld",&n);

for(i=1;i<=n;i++)

{

call=prime(i);

if(call)

{

a[j]=i;

j++;

total++;

}

}

for(i=0;i<total;i++)

{

for(j=0;j<total;j++)

{

bitcheck=bits(a[j]);

connect=a[i]*pow(10,bitcheck)+a[j];

printf("%ld\n",connect);

recheck=prime(connect);

if(recheck)

{

count++;

}

}

}

printf("%ld\n",count);

return 0; }

link
This answer is marked "community wiki".

answered 01 Aug '17, 10:04

blazedxi's gravatar image

4★blazedxi
263
accept rate: 0%

edited 01 Aug '17, 10:16

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×27
×23
×2
×2

question asked: 29 Jul '17, 14:53

question was seen: 1,315 times

last updated: 01 Aug '17, 11:51