Problem Description:
Some prime numbers can be expressed as Sum of other consecutive prime numbers.
For example
5 = 2 + 3
17 = 2 + 3 + 5 + 7
41 = 2 + 3 + 5 + 7 + 11 + 13
Your 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.
Write code to find out number of prime numbers that satisfy the above mentioned property in a given range.
Input Format:
For example
5 = 2 + 3
17 = 2 + 3 + 5 + 7
41 = 2 + 3 + 5 + 7 + 11 + 13
Your 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.
Write code to find out number of prime numbers that satisfy the above mentioned property in a given range.
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.
Print the total number of all such prime numbers which are less than or equal to N.
Sample Input and Output
| SNo. | Input | Output | Comment |
|---|---|---|---|
| 1 | 20 | 2 | (Below 20, there are 2 such numbers: 5 and 17). 5=2+3 17=2+3+5+7 |
| 2 | 15 | 1 |
Program:
#include <stdio.h>
int prime(int b)
{
int j,cnt;
cnt=1;
for(j=2;j<=b/2;j++)
{
if(b%j==0)
cnt=0;
}
if(cnt==0)
return 1;
else
return 0;
}
int main() {
int i,j,n,cnt,a[25],c,sum=0,count=0,k=0;
scanf("%d",&n);
for(i=2;i<=n;i++)
{
cnt=1;
for(j=2;j<=n/2;j++)
{
if(i%j==0)
cnt=0;
}
if(cnt==1)
{
a[k]=i;
k++;
}
}
for(i=0;i<k;i++)
{
sum=sum+a[i];
c= prime(sum);
if(c==1)
count++;
}
printf("%d",count);
return 0;
}
Output:
20
2
You can also run it on a online IDE: https://ide.geeksforgeeks.org/XcOKzTd4Ik
If you have any doubt you can contact me or comment it below! Your comments and feedbacks are also welcomed!! Cheers!!
Related Links: Jumble with Numbers
Related Links: Jumble with Numbers
one test case is being timed out
ReplyDeletecan you pls say which one is that? let me check!
DeleteIt Will always time out for n greater than 1000
ReplyDeleteIt's wrong, if I enter the value of 70 gives me 7, if income 80 gives me 8 and with 100 gives me 6. I'll leave the code in Python if you're interested.
ReplyDeletedef esPrimo(num): #Funcion que determina si es primo
if num < 2: return False
for i in range (2, num):
if num % i == 0: return False
return True
n = int(input()) #Número ingresado por el usuario
primos = [i for i in range(1, n) if esPrimo(i)]
cont = 0
for i in range(len(primos)):
suma = sum(primos[:i+2])
if esPrimo(suma) and suma < n:
cont += 1
print(cont)
no proper indentation
DeleteI can't understand the program
ReplyDeletepackage Second;
ReplyDeleteimport java.util.*;
public class Second{
public static void main(String[] args) {
int n;
Scanner in = new Scanner(System.in);
n = in.nextInt();
int[] a = new int[n];
int index = 0,count = 0,sum=0;
for(int i=2; i<=n; i++) {
if(i==2||i==3) {
//System.out.println(i);
a[index] = i;
index++;
}else if(i%2==0||i%3==0) {
continue;
}else {
//System.out.println(i);
a[index] = i;
index++;
}
}
//sum = 5;
for(int i=0; i=5&&sum<n) {
//System.out.println(sum);
count++;
}
}
}if(sum<n) {sum=0;}
else {break;}
}
System.out.println(count/3);
}
}
Is the same program available for python?
ReplyDelete
ReplyDeletek = []
sum = 2
for i in range(2,100):
if i%2!=0:
sum=sum+i
if sum%2!=0:
if sum<=100:
k.append(sum)
print(k)
Can u explain
DeleteCan you explain the logic
ReplyDeletesince the constarints are 2<N<12000000000000 some test cases results in Timelimit errors
ReplyDeleteCan someone give the optimized code which can even work for n=12000000000 plzz
ReplyDeletewell the above code doesn't work for value 10,6 and also takes more time to compile so I coded a new code which is much better than this one
ReplyDelete#include
int main()
{
int a,i,j,k=0,count1=0,count2=0,count3=0;
int arr[30],ar[30],sum=0;
scanf("%d",&a);
for(j=2;j<=a;j++)
{
for(i=2;i<=j;i++)
{
if(j%i==0)
{
count1++;
}
}
if(count1==1)
{
arr[k]=j;
k++;
}
count1=0;
}
for(i=0;i<k;i++)
{
sum=sum+arr[i];
ar[i]=sum;
}
for(i=1;i<k;i++)
{
for(j=2;j<=a;j++)
{
if(ar[i]%j==0)
{
if(ar[i]<=a)
{
count2++;}
}
}
if(count2==1)
{
count3++;
}
count2=0;
}
printf("%d",count3);
}