Member Avatar for ahmed.talha.16

Hello! can anybody please tell me the formula through which i can make the prime number program. I couldn't found the logic of it.

  • 5 Contributors
  • 4 Replies
  • 365 Views
  • 16 Hours Discussion Span
  • Latest Post Latest Post by uttkarshsing
jwenting commented: lazy homework kiddo -3

Dani AI

Generated

Prime numbers are integers greater than 1 that have no positive divisors other than 1 and themselves. Note: 1 is not prime (contrary to ). For a single-number test it suffices to try divisors only up to the square root of the number because any factor larger than sqrt(n) pairs with one smaller than sqrt(n).

The idea shown by captures that sqrt(n) observation, but the implementation has a few problems: it reads a floating value, uses an int flag instead of a boolean, keeps testing after finding a divisor, and tests every number instead of skipping obvious non-candidates. ’s suggestion to stop early and use clearer types is correct.

A simple, efficient and idiomatic approach:

  • handle n <= 1 (not prime), and small bases 2 and 3,
  • eliminate multiples of 2 and 3,
  • then test divisors of the form 6k ± 1 up to sqrt(n).
    This checks far fewer candidates than checking every odd number and returns as soon as a divisor is found (early exit).
import java.util.Scanner;

public class PrimeCheck {
    public static boolean isPrime(long n) {
        if (n <= 1) return false;
        if (n <= 3) return true;
        if (n % 2 == 0 || n % 3 == 0) return false;
        for (long i = 5; i * i <= n; i += 6) {
            if (n % i == 0 || n % (i + 2) == 0) return false;
        }
        return true;
    }

    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        System.out.print("Enter an integer: ");
        long n = s.nextLong();
        System.out.println(n + " is " + (isPrime(n) ? "prime" : "not prime"));
    }
}

Notes: this method is O(sqrt(n)). For generating many primes up to N use a sieve. For very large integers (beyond 64-bit) use Java’s BigInteger.isProbablePrime or a Miller-Rabin implementation. Also always treat negatives, 0 and 1 as non-prime.

Recommended Answers

All 4 Replies

Member Avatar for subhraakasuny 
import java.io.*;

/*Prime number is that kind of number
which divisible by only 1 and itself*/

public class PrimeNumber 
{
    public static void main(String args[])throws IOException
    {
        double num;
        int flag=0;
        System.out.println("Enter the number to check whether it is prime or not:");
        BufferedReader bufferedReader=new BufferedReader(new InputStreamReader(System.in));
        num=Double.parseDouble(bufferedReader.readLine());
                                                                              /*so we have to check starting from 2 upto square root of the number
 you can check manually,if a number is not going to be divisible upto 
the square root of the same number starting from 2,then it will not
 going to be divided by any other number above than the square root and lesser that the input*/
        for(int i=2;i<=Math.sqrt(num);i++)
        {
            if(num%i==0)
            {
                flag=1;
            }
        }
        if(flag==0)
            System.out.println(num +" is a prime number");
        else
            System.out.println(num +"is not a prime number");

    }
}
commented: don't help homework kiddos -3
Member Avatar for JamesCherrill

If OP really doesn't have sufficient ability or initiative to find information on prime number programs on the web then simply giving them something to copy & paste into their homework is helping nobody. Not their teacher, not a potential employer, not their hard working colleagues, and least of all not the OP.

ps: Anyone thinking of using subhraakasuny's code should also be aware that it's a poor example of Java code. An int called "flag" that just has values 0 and 1 clearly identifies someone who (a) doesn't care about variable naming and (b) hasn't heard of booleans. It's also inefficient (tries modulo by every number when it only needs primes or at the very least just odd numbers after two; keeps going even after proving num is not prime).

Edited by JamesCherrill
commented: Being a beginner,It is really helpful to me to understand the fault. +0
Member Avatar for jwenting

well, it may help him get a job for a few weeks until he gets fired for incompetence. Which might yield him a paycheck of unearned wages for that period, at the expense of qualified people who now end up not only unemployed and poorer but suspect of being unqualified as well.

Member Avatar for uttkarshsing

Prime no is a no which is divide by 1 and its own.

E.G. 1,2,3,5,7,11.....

commented: 1 is not a prime number +0
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.