Find Prime Nodes Sum Count in Non-Binary Tree
Implementation
// Writing a C++ program that will count the nodes which contain the prime digit and hold the sum of the weights in a binary tree
#include <bits/stdc++.h>
using namespace std;
int MAX = 1000000;
int answerr = 0;
Vecc<int> graph[100];
Vecc<int> weight(100);
// Creating a function that will create the sieve and check whether it is prime or not.
void SieveOfEratosthenes(
bool prime[], int p_size)
{
// If the value we get is false, then it will indicate that the value is not prime
prime[0] = false;
prime[1] = false;
for (int p = 2; p * p <= p_size; p++) {
//If the prime say [p] is not changed, it is a prime number.
if (prime[p]) {
// We have to progress all the multiples that we have of p, and then we have to put them to the non-prime number
for (int i = p * 2;
i <= p_size;
i += p)
prime[i] = false;
}
}
}
// Now, we have to create a function that will give us the sum of the digits of the n
int digitSum(int n)
{
int sum = 0;
while (n) {
sum += n % 10;
n = n / 10;
}
return sum;
}
// Now, we have to create a function for the dfs
void dfs(int __nod,
int parent,
bool prime[])
{
//If the sum of the digits turns out to be the weight of the current node, then it is prime, and then we have to increase the answerer.
int sum = digitSum(weight[__nod]);
if (prime[sum])
answerr += 1;
for (int to : graph[__nod]) {
if (to == parent)
continue;
dfs(to, __nod, prime);
}
}
// writing the main code to test the above functions
int main()
{
// Extracting the weight of the nodes
weight[1] = 144;
weight[2] = 1234;
weight[3] = 21;
weight[4] = 5;
weight[5] = 77;
// Evaluating the edges of the tree
graph[1].push_back(2);
graph[2].push_back(3);
graph[2].push_back(4);
graph[1].push_back(5);
bool prime[MAX];
memset(prime, true, sizeof(prime));
SieveOfEratosthenes(prime, MAX);
dfs(1, 1, prime);
cout << answerr;
return 0;
}
Output:
Example 2)
// Writing a C# program that will count the nodes which contain the prime digit and hold the sum of the weights in a binary tree
using System;
using System.Collections.Generic;
class TPT{
static int MAX = 1000000;
static int answerr = 0;
static List<int> []graph =
new List<int>[100];
static int []weight = new int[100];
// Creating a function that will create the sieve and check whether it is prime or not.
static void SieveOfEratosthenes(bool []prime,
int p_size)
{
// If the value we get is false, then it will indicate that the value is not prime
prime[0] = false;
prime[1] = false;
for (int p = 2; p * p <= p_size; p++)
{
// In case, the prime say [p] is not changed, then it is a prime number.
if (prime[p])
{
// We have to progress all the multiples that we have of p, and then we have to put them to the non-prime number
for (int i = p * 2;
i < p_size; i += p)
prime[i] = false;
}
}
}
// Now, we have to create a function that will give us the sum of the digits of the n
static int digitSum(int n)
{
int sum = 0;
while (n > 0)
{
sum += n % 10;
n = n / 10;
}
return sum;
}
// Now, we have to create a function for the dfs
static void dfs(int __nod,
int parent,
bool []prime)
{
//If the sum of the digits turns out to be the weight of the current node, then it is prime, and then we have to increase the answer.
int sum = digitSum(weight[__nod]);
if (prime[sum])
answerr += 1;
foreach (int to in graph[__nod])
{
if (to == parent)
continue;
dfs(to, __nod, prime);
}
}
// writing the main code to test the above functions
public static void Main(String[] args)
{
// Extracting the weight of the nodes
weight[1] = 144;
weight[2] = 1234;
weight[3] = 21;
weight[4] = 5;
weight[5] = 77;
for (int i = 0; i < graph.Length; i++)
graph[i] = new List<int>();
// Evaluating the edges of the tree
graph[1].Add(2);
graph[2].Add(3);
graph[2].Add(4);
graph[1].Add(5);
bool []prime = new bool[MAX];
for (int i = 0; i < prime.Length; i++)
prime[i] = true;
SieveOfEratosthenes(prime, MAX);
dfs(1, 1, prime);
Console.Write(answerr);
}
}Output:
Example 3)
// Writing a Java program that will count the nodes which contain the prime digit and hold the sum of the weights in a binary tree
import java.util.*;
class TPT{
static int MAX = 1000000;
static int answerr = 0;
static Vecc<Integer> []graph =
new Vecc[100];
static int []weight = new int[100];
// Creating a function to create the sieve and check whether it is prime.
static void SieveOfEratosthenes(boolean prime[],
int p_size)
{
//If the prime say [p] is not changed, it is a prime number.
prime[0] = false;
prime[1] = false;
for (int p = 2; p * p <= p_size; p++)
{
// We have to progress all the multiples that we have of p, and then we have to put them to the non-prime number
if (prime[p])
{
// We have to progress all the multiples that we have of p, and then we have to put them to the non-prime number
for (int i = p * 2;
i < p_size; i += p)
prime[i] = false;
}
}
}
// Now, we have to create a function that will give us the sum of the digits of the n
static int digitSum(int n)
{
int sum = 0;
while (n > 0)
{
sum += n % 10;
n = n / 10;
}
return sum;
}
// Now, we have to create a function for the dfs
static void dfs(int __nod,
int parent,
boolean prime[])
{
//If the sum of the digits turns out to be the weight of the current node, then it is prime, and then we have to increase the answer.
int sum = digitSum(weight[__nod]);
if (prime[sum])
answerr += 1;
for (int to : graph[__nod])
{
if (to == parent)
continue;
dfs(to, __nod, prime);
}
}
// writing the main code to test the above functions
public static void main(String[] args)
{
// Extracting the weight of the nodes
weight[1] = 144;
weight[2] = 1234;
weight[3] = 21;
weight[4] = 5;
weight[5] = 77;
for (int i = 0; i < graph.length; i++)
graph[i] = new Vecc<Integer>();
// Evaluating the edges of the tree
graph[1].add(2);
graph[2].add(3);
graph[2].add(4);
graph[1].add(5);
boolean []prime = new boolean[MAX];
Arrays.fill(prime, true);
SieveOfEratosthenes(prime, MAX);
dfs(1, 1, prime);
System.out.print(answerr);
}
}Output:
Example 4)
# Writing a Python program that will count the nodes which contain the prime digit and hold the sum of the weights in a binary tree
from typing import List
MAX = 1000000
answerr = 0
graph = [[] for _ in range(100)]
weight = [0 for _ in range(100)]
# Creating a function that will create the sieve and check whether it is prime.
def SieveOfEratosthenes(prime: List[bool], p_size: int) -> None:
# If the value we get is false, then it will indicate that the value is not prime
prime[0] = False
prime[1] = False
p = 2
while p * p <= p_size:
# If the prime say [p] is not changed, it is a prime number.
if (prime[p]):
# We have to progress all the multiples that we have of p, and then we have to put them to the non-prime number
for i in range(p * 2, p_size + 1, p):
prime[i] = False
p += 1
# Now, we have to create a function that will give us the sum of the digits of the n
def digitSum(n: int) -> int:
sum = 0
while (n):
sum += n % 10
n = n // 10
return sum
# Now, we have to create a function for the dfs
def dfs(__nod: int, parent: int, prime: List[bool]) -> None:
global answerr
# If the sum of the digits turns out to be the weight of the current node, then it is prime, and then we have to increase the answer.
sum = digitSum(weight[__nod])
if (prime[sum]):
answerr += 1
for to in graph[__nod]:
if (to == parent):
continue
dfs(to, __nod, prime)
# Writing the main code to test the above functions
if __name__ == "__main__":
# Extracting the weight of the nodes
weight[1] = 144
weight[2] = 1234
weight[3] = 21
weight[4] = 5
weight[5] = 77
# Evaluating the edges of the tree
graph[1].append(2)
graph[2].append(3)
graph[2].append(4)
graph[1].append(5)
prime = [True for _ in range(MAX + 1)]
SieveOfEratosthenes(prime, MAX)
dfs(1, 1, prime)
print(answerr)Output:
Example 5)
<script>
// Writing a Javascript program that will count the nodes which contain the prime digit and hold the sum of the weights in a binary tree
let MAX = 1000000;
let answerr = 0;
let graph = [];
for(let i = 0; i < 100; i++){
graph.push([])
}
console.log(graph)
let weight = new Array(100);
// Creating a function to create the sieve and check whether it is prime.
function SieveOfEratosthenes(prime, p_size)
{
// If the value we get is false, then it will indicate that the value is not prime
prime[0] = false;
prime[1] = false;
for (let p = 2; p * p <= p_size; p++) {
//If the prime say [p] is not changed, it is a prime number.
if (prime[p]) {
// We have to progress all the multiples that we have of p, and then we have to put them to the non-prime number
for (let i = p * 2;
i <= p_size;
i += p)
prime[i] = false;
}
}
}
// Now, we have to create a function that will give us the sum of the digits of the n
function digitSum(n)
{
let sum = 0;
while (n) {
sum += n % 10;
n = Math.floor(n / 10);
}
return sum;
}
// Now, we have to create a function for the dfs
function of(__nod, parent, prime)
{
// In case the sum of the digits turns out to be the weight of the current node, then it is prime, and then we have to increase the answer.
let sum = digitSum(weight[__nod]);
if (prime[sum])
answerr += 1;
for (let to of graph[__nod]) {
if (to == parent)
continue;
dfs(to, __nod, prime);
}
}
// writing the main code to test the above functions
// Extracting the weight of the nodes
weight[1] = 144;
weight[2] = 1234;
weight[3] = 21;
weight[4] = 5;
weight[5] = 77;
// Evaluating the edges of the tree
graph[1].push(2);
graph[2].push(3);
graph[2].push(4);
graph[1].push(5);
let prime = new Array(MAX);
prime.fill(true)
SieveOfEratosthenes(prime, MAX);
dfs(1, 1, prime);
document.write(answerr);
// This code is contributed by TPTking
</script>Output:
