Data Structure and Algorithm | Functions and Recursions | Codewindow.in

Question 1:

A positive integer d is said to be a factor of another positive integer N if when N is divided by d, the remainder obtained is zero. For example, for number 12, there are 6 factors 1, 2, 3, 4, 6, 12. Every positive integer k has at least two factors, 1 and the number k itself. Give two positive integers N and k, write a program to print the kth largest factor of N.

Input Format:
The input is a comma-separated list of positive integer pairs (N, k)

Output Format:
The kth highest factor of N. If N does not have k factors, the output should be 1.

Constraints:
1<N<10000000000. 1<k<600. You can assume that N will have no prime factors which are larger than 13.

Sample Input 1:
12,3

Sample Output 1:
4

Explanation:
N is 12, k is 3. The factors of 12 are (1,2,3,4,6,12). The highest factor is 12 and the third largest factor is 4. The output must be 4

Sample Input 2:
30,9

Sample Output 2:
1

Explanation:
N is 30, k is 9. The factors of 30 are (1,2,3,5,6,10,15,30). There are only 8 factors. As k is more than the number of factors, the output is 1.

Solution: In C

import java.io.*;
import java.util.*;

class GFG {
    static int KthLargestFactor(int n, int k)
    {
        for (int i = n; i>0; i--) {
            if (n % i == 0)
                k--;
            if (k == 0)
                return i;
        }
        return 1;
    }

    public static void main(String[] args) throws Exception
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str = br.readLine().split(",");
        int N = Integer.parseInt(str[0]);
        int K = Integer.parseInt(str[1]);
        System.out.println(KthLargestFactor(N, K));
    }
}

Solution: In Java

import java.io.*;
import java.util.*;

class GFG {
    static int KthLargestFactor(int n, int k)
    {
        for (int i = n; i>0; i--) {
            if (n % i == 0)
                k--;
            if (k == 0)
                return i;
        }
        return 1;
    }

    public static void main(String[] args) throws Exception
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str = br.readLine().split(",");
        int N = Integer.parseInt(str[0]);
        int K = Integer.parseInt(str[1]);
        System.out.println(KthLargestFactor(N, K));
    }
}

Solution: In Python 3

def KthLargestFactor(n, k):
    for i in range(n, 0, -1):
        if n % i == 0:
            k -= 1
        if k == 0:
            return i
    return 1

st = str(input()).split(",")
N = int(st[0])
K = int(st[1])
print(KthLargestFactor(N, K))

Question 2:

Some prime numbers can be expressed as a sum of other consecutive prime numbers. For example 5 = 2 + 3, 17 = 2 + 3 + 5 + 7, 41 = 2 + 3 + 5 + 7 + 11 + 13. Now the task is to find out how many prime numbers which satisfy this property are present in the range 3 to N subject to a constraint that summation should always start with number 2.

Input Format:
First line contains a number N

Output Format:
Print the total number of all such prime numbers which are less than or equal to N.

Constraints:
2<N<=12,000,000,000

Sample Input 1 :
20

Sample Output 1 :
2

Explanation :
5 = 2+3
17 = 2+3+5+7

Sample Input 2 :
15

Sample Output 2 :
1

Explanation :
5 = 2+3

Solution: In C

if a>b:
    print("Hi")

Solution: In Java

import java.util.Scanner;

class Main {
  static int prime(int b) {
    int j,cnt;
    cnt=1;
    for (j = 2; j &lt;= b/2; j++) {
      if(b%j==0)
      cnt=0;
    }
    if(cnt==0)
      return 1;
    else
      return 0;
  }

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int i,j,n=0,cnt,c=0,sum=0,count=0,k=0;
    Main t = new Main();
    int[] a = new int[25];
    n = sc.nextInt();

    for (i = 2; i &lt;=n ; i++) {
      cnt=1;
      for (j = 2; j &lt;= n/2; j++) {
        if(i%j==0)
          cnt=0;
      }

      if(cnt==1) {
        a[k]=i;
        k++;
      }
    }

    for (i = 0; i &lt; k; i++) {
      sum=sum+a[i];
      c=t.prime(sum);
      if(c==1)
        count++;
    }
    System.out.println(count);
  }
}

Solution: In Python 3

num = int(input())
arr = []
sum = 0
count = 0
if num &gt; 1:
    for i in range(2, num + 2):
        for j in range(2, i):
            if i % j == 0:
                break
            else:
                arr.append(i)
                

def is_prime(sum):
    for i in range(2, (sum // 2) +2):
        if sum % i == 0:
            return False
    return True
for i in range(0, len(arr)):
    sum = sum + arr[i]
    if sum &lt;= num:
        if is_prime(sum):
            count = count + 1
print(count)

Leave a Comment

Your email address will not be published. Required fields are marked *