Tuesday, September 28, 2010

Find a prime number in Java - Algorithm

Simple? Oh yea, it is! But to what extent we can programmatically optimise it? Le'me show you -

Some theory

A prime number (or a prime) is a natural number greater than 1 that has no positive divisors other than 1 and itself.

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31

One brute force is to loop through i:0->n : and find out if n is divisible by i. Complexity is O(n) here. But can we optimize it.

Yes. Here are the rules to find a prime number -

  • Number has to be > 1
  • Number cannot be even (Other than 2. 2 is prime). Because even numbers are always divisible by 2. This reduces the number to half.
  • If you list out all of the factors of a number, the square root will always be in the middle. So when checking factors, we need not check 0 to n. Check only upto square root of n, that should cover all possible factors. This further reduces the comparisons to sq. root of n, and that too excluding all evens.

Java Code

package main.java.algo;

public class IsPrime {
 
 // if you list out all of the factors of a number, the square root will always be in the middle
 
 public static void main(String[] args) {
  System.out.println(Integer.valueOf('c'));
 }
 
 // checks whether an int is prime or not.
 boolean isPrime(int n) {
  
  //prime is natural number greater than 1
  if(n <= 1)
   return false;
  
  // but ignore 2, as 2 is a prime number
  if(n == 2)
   return true;
  
  // check if n is a multiple of 2
  if (n % 2 == 0)
   return false;
  
  // if not, then just check the odds : note -> i += 2
  // check only upto square root of a number
  for (int i = 3; i * i <= n; i += 2) {
   if (n % i == 0)
    return false;
  }
  
  return true;
 }

}




4 comments:

  1. hi, I m new to programing.

    program above: I understand up to if (n % 2 == 0) (its to get rid of even numbers?) return false; also I understand the for loop itself. but not i*i part.

    if n=8;

    for(position = 3; position*position = 9; 9+2=11)

    if(8 % 3 == 0) remainder is not zero so its false
    return false;
    I get all that. but why i*i I do not understand the logic. i m slow :( lol. if you could help me understand it would b great help.

    ReplyDelete
    Replies
    1. i * i <= n is same as i<=SQRT(n) . so better to use i*i instead of calling SQRT function. because function call has its own cost in term of time complexity.

      Delete
    2. và biến mất một cách kỳ bí .
      Ngân long Ly Sát kinh ngạc đến ngây người , nàng cũng không chứng kiến ánh mắt tràn đầy sát khí của Tử . Việc hắc long bị giết chết dễ dàng khiến cho nàng vô cùng sợ hãi , hơn nữa những lời cuối cùng của Dạ Tinh Hủ cứ không ngừng vang vọng trong đầu của nàng . “ Tử tinh bỉ mông , chẳng lẽ chính là tử tinh bỉ mông trong truyền thuyết ? Là thượng cổ thần thú đứng đầu của thú nhân tộc , có thể sánh ngang với thần tháđồng tâm
      game mu
      cho thuê nhà trọ
      cho thuê phòng trọ
      nhac san cuc manh
      số điện thoại tư vấn pháp luật miễn phí
      văn phòng luật
      tổng đài tư vấn pháp luật
      dịch vụ thành lập công ty
      http://we-cooking.com/
      chém gió
      trung tâm tiếng anhnh cự long – đế vương tử tinh bỉ mông thật sao ? “ .
      “ Không sai , ngươi đã đoán đúng rồi . Cho nên hôm nay ngươi cũng phải chết . Ta không thể để long tộc biết được tung tích của ta “ . Thanh âm lạnh như băng của Tử kèm theo sát khí mãnh liệt khiến Ly Sát bừng tỉnh , mỗi bước chân của Tử chậm rãi tiến lại gần là mỗi lần khiến nàng thót tim , toàn thân không ngừng run rẩy kịch liệt , thậm chí trong đầu còn không có cả ý nghĩ phản kháng lại .
      Ánh mắt nàng tràn đầy sự tuyệt vọng , bởi vì nàng biết bản thân cho dù có bay lên cũng không thoát được trong khi ma pháp công kích đối với Tử hoàn toàn không có hiệu quả . Huống chi ma lực của nàng chỉ còn lại chưa đến ba thành , nhìn kết cục của hắc long , nàng cũng biết bản thân không có lấy một tia cơ hội mỏng manh để sống sót .
      Thân hình Tử cẫn chậm rãi đến gần , tử quang không ngừng lóe ra kèm theo khí thế bức nhân khiến cho Ly Sát cảm thấy không thể thở nổi . Tử tinh kiếm trong tay Tử chậm rãi giơ lên , long lân của hắc long còn

      Delete