Woodall Primes are prime numbers that are also Woodall number.
Find the Woodall prime numbers less than N
Given a number N, print all Woodall primes smaller than or equal to N.
Examples:
Input: N = 10
Output: 7
Input: N = 500
Output: 7, 23, 383
Approach: The idea is to use Sieve of Eratosthenes to check that a number is prime or not efficiently. Then, Iterate over integers from 1 to N, and for every number check that if it is prime or not and it is Woodall number or not. If a number is prime also a Woodall number, Then it a Woodall prime.
Below is the implementation of above algorithm:
C++
// C++ implementation to print all Woodall// primes smaller than or equal to n.#include <bits/stdc++.h>using namespace std;// Function to check if a number// N is Woodallbool isWoodall(int x){ // If number is even, return false. if (x % 2 == 0) return false; // If x is 1, return true. if (x == 1) return true; x = x + 1; // Add 1 to make x even // While x is divisible by 2 int p = 0; while (x % 2 == 0) { // Divide x by 2 x = x / 2; // Count the power p = p + 1; // If at any point power and // x became equal, return true. if (p == x) return true; } return false;}// Function to generate all primes and checking// whether number is Woodall or notvoid printWoodallPrimesLessThanN(int n){ // Create a boolean array "prime[0..n]" and // initialize all entries it as true. A value // in prime[i] will finally be false if i is // Not a prime, else true. vector<bool> prime(n + 1, true); int p = 2; while (p * p <= n) { // If prime[p] is not changed, // then it is a prime if (prime[p]) // Update all multiples of p for (int i = p * 2; i <= n; i += p) prime[i] = false; p += 1; } // Print all Woodall prime numbers for (p = 2; p <= n; p++) { // checking whether the given number // is prime Woodall or not if (prime[p] && isWoodall(p)) cout << p << " "; }}// Driver Codeint main(){ int n = 1000; printWoodallPrimesLessThanN(n);}// This code is contributed by phasing17 |
Java
// Java implementation to print all Woodall// primes smaller than or equal to n.import java.io.*;import java.util.*;class GFG{ // Function to check if a number // N is Woodall static Boolean isWoodall(int x) { // If number is even, return false. if (x % 2 == 0) return false; // If x is 1, return true. if (x == 1) return true; x = x + 1; // Add 1 to make x even // While x is divisible by 2 int p = 0; while (x % 2 == 0) { // Divide x by 2 x = x / 2; // Count the power p = p + 1; // If at any point power and // x became equal, return true. if (p == x) return true; } return false; } // Function to generate all primes and checking // whether number is Woodall or not static void printWoodallPrimesLessThanN(int n) { // Create a boolean array "prime[0..n]" and // initialize all entries it as true. A value // in prime[i] will finally be false if i is // Not a prime, else true. ArrayList<Boolean> prime = new ArrayList<Boolean>(); for (int i = 0; i <= n; i++) prime.add(true); int p = 2; while (p * p <= n) { // If prime[p] is not changed, // then it is a prime if (prime.get(p)) // Update all multiples of p for (int i = p * 2; i <= n; i += p) prime.set(i,false); p += 1; } // Print all Woodall prime numbers for (p = 2; p <= n; p++) { // checking whether the given number // is prime Woodall or not if (prime.get(p) && isWoodall(p)) System.out.print(p + " "); } } // Driver Code public static void main (String []args) { int n = 1000; printWoodallPrimesLessThanN(n); }}// This code is contributed by Pushpesh Raj |
Python3
# Python3 implementation to print all Woodall # primes smaller than or equal to n. # Function to check if a number # N is Woodall def isWoodall(x) : # If number is even, return false. if (x % 2 == 0) : return False # If x is 1, return true. if (x == 1) : return True x = x + 1 # Add 1 to make x even # While x is divisible by 2 p = 0 while (x % 2 == 0) : # Divide x by 2 x = x / 2 # Count the power p = p + 1 # If at any point power and # x became equal, return true. if (p == x) : return True return False # Function to generate all primes and checking # whether number is Woodall or not def printWoodallPrimesLessThanN(n): # Create a boolean array "prime[0..n]" and # initialize all entries it as true. A value # in prime[i] will finally be false if i is # Not a prime, else true. prime = [True] * (n + 1); p = 2; while (p * p <= n): # If prime[p] is not changed, # then it is a prime if (prime[p]): # Update all multiples of p for i in range(p * 2, n + 1, p): prime[i] = False; p += 1; # Print all Woodall prime numbers for p in range(2, n + 1): # checking whether the given number # is prime Woodall or not if (prime[p] and isWoodall(p)): print(p, end = " "); # Driver Code n = 1000; printWoodallPrimesLessThanN(n) |
C#
// C# implementation to print all Woodall// primes smaller than or equal to n.using System;using System.Collections.Generic;class GFG{ // Function to check if a number // N is Woodall static bool isWoodall(int x) { // If number is even, return false. if (x % 2 == 0) return false; // If x is 1, return true. if (x == 1) return true; x = x + 1; // Add 1 to make x even // While x is divisible by 2 int p = 0; while (x % 2 == 0) { // Divide x by 2 x = x / 2; // Count the power p = p + 1; // If at any point power and // x became equal, return true. if (p == x) return true; } return false; } // Function to generate all primes and checking // whether number is Woodall or not static void printWoodallPrimesLessThanN(int n) { // Create a boolean array "prime[0..n]" and // initialize all entries it as true. A value // in prime[i] will finally be false if i is // Not a prime, else true. List<bool> prime = new List<bool>(); for (int i = 0; i <= n; i++) prime.Add(true); int p = 2; while (p * p <= n) { // If prime[p] is not changed, // then it is a prime if (prime[p]) // Update all multiples of p for (int i = p * 2; i <= n; i += p) prime[i] = false; p += 1; } // Print all Woodall prime numbers for (p = 2; p <= n; p++) { // checking whether the given number // is prime Woodall or not if (prime[p] && isWoodall(p)) Console.Write(p + " "); } } // Driver Code public static void Main(string[] args) { int n = 1000; printWoodallPrimesLessThanN(n); }}// This code is contributed by phasing17 |
Javascript
// Python3 implementation to print all Woodall // primes smaller than or equal to n. // Function to check if a number // N is Woodall function isWoodall(x) { // If number is even, return false. if (x % 2 == 0) return false // If x is 1, return true. if (x == 1) return true x = x + 1 // Add 1 to make x even // While x is divisible by 2 let p = 0 while (x % 2 == 0) { // Divide x by 2 x = x / 2 // Count the power p = p + 1 // If at any point power and // x became equal, return true. if (p == x) return true } return false}// Function to generate all primes and checking // whether number is Woodall or not function printWoodallPrimesLessThanN(n) { // Create a boolean array "prime[0..n]" and // initialize all entries it as true. A value // in prime[i] will finally be false if i is // Not a prime, else true. let prime = new Array(n + 1).fill(true) let p = 2; while (p * p <= n) { // If prime[p] is not changed, // then it is a prime if (prime[p]) // Update all multiples of p for (var i = p * 2; i <= n; i += p) prime[i] = false; p += 1; } // Print all Woodall prime numbers for (p = 2; p <= n; p ++) { // checking whether the given number // is prime Woodall or not if (prime[p] && isWoodall(p)) process.stdout.write(p + " "); }} // Driver Code let n = 1000; printWoodallPrimesLessThanN(n)// This code is contributed by phasing17 |
Output:
7 23 383
Time Complexity: O(n*log(n))
Auxiliary Space: O(n)
Share your thoughts in the comments
