• Welcome to Bashguru

    Linux is one of popular version of UNIX operating System. It is open source as its source code is freely available. It is free to use. Linux was designed considering UNIX compatibility. It's functionality list is quite similar to that of UNIX and become very popular over the last several years. Our Basic motive is to provide latest information about Linux Operating system.

  • Python Programming

    Python is a comparatively simple programming language, compared to c++. Although some of the benefits of c++ are abstracted away in python, they are replaced with an overall easier to learn language with many “intuitive” features. For this reason it is common and recommended by most professionals that people new to programming start with python.

  • Perl Programming

    Perl is an open-source, general-purpose interpreted programming language. Used often for CGI, Perl is also used for graphics programming, system administration, network programming, finance, bioinformatics, and other applications. The Perl languages borrow features from other programming languages including C, shell scripting (sh), AWK, and sed. They provide powerful text processing facilities without the arbitrary data-length limits of many contemporary UNIX command line tools, facilitating easy manipulation of text files.

  • Android

    Android is an operating system based on the Linux kernel, and designed primarily for touch screen mobile devices such as smart phones and tablet computers. Android is a Linux-based software system, and similar to Linux, is free and open source software. This means that other companies can use the Android operating developed by Google and use it in their mobile devices.Android gives you a world-class platform for creating apps and games for Android users everywhere, as well as an open marketplace for distributing to them instantly.

Friday, June 24, 2011

Posted by venu k
9 comments | 10:24 PM
 
In number theory, the prime factors of a positive integer are the prime numbers
that divide that integer exactly, without leaving a remainder. The process of
finding these numbers is called integer factorization, or prime factorization.
The fundamental theorem of arithmetic says that every positive integer has a
unique prime factorization.

Example:

The prime factors of 330 are 2, 3, 5 and 11:

               330 = 2 × 3 × 5 × 11

 There is no other possible set of prime numbers that can be multiplied to
make 330.

 You can find prime factors of a number using UNIX/Linux utility factor. This is
a very convenient and cool UNIX command. Here is its syntax:

$ factor 330
330: 2 3 5 11
$ factor 2121977
2121977: 11 11 13 19 71

 Many Algorithms have been devised for determining the Prime factors of a given
number. They vary quite a bit in sophistication and complexity. It is very diff-
icult to build a general-purpose algorithm for this computationally "hard" prob-
lem, so any additional information which is known about the number in question
or its factors can often be used to save a large amount of time.

 Here I am providing a shell script to find prime factors of a positive integer.
This script does most factorizations within a second. In the worst case scenario
(for some large semi-primes with more than 6-digit factors) factorization will
take a couple of minutes to hours.

#!/bin/bash # SCRIPT: primefactors.sh # USAGE : primefactors.sh <Positive Integer> # PURPOSE: Produces prime factors of a given number. # ############################################################################### # Arguments Checking # ############################################################################### if [ $# -ne 1 ] then echo "Usage: scriptname <Positive Integer>" exit 1 fi expr $1 + 1 &>/dev/null if [ $? -ne 0 ] then echo "Sorry, You supplied non numerical value" exit 1 fi [ $1 -lt 2 ] && echo "Values < 2 are not prime numbers" && exit 1 num=$1 ############################################################################### # Functions # ############################################################################### # To know how to find prime number check bellow link: # Shell script to find prime number # Bellow function finds supplied argument is a prime or not. primenumber() { primenum=$1 for ((counter2=2;$((counter2*counter2))<=$primenum;counter2++)) do if [ $((primenum%counter2)) -eq 0 ] then return 1 fi done return 0 } primefind() { # It's good to check that the number it self is a prime or not before going to # find prime factors of a number. Comment out bellow line and supply a prime # number or semi-prime, you will find the difference. # Ex: primefactors.sh 2121979 primenumber $1 && echo "$1" && exit 0 for ((counter1=$2;counter1<=$1;counter1++)) do primenumber $counter1 && factorcheck $1 $counter1 && break done } factorcheck() { prime=$2 newnum=$1 remainder=$((newnum%prime)) if [ $remainder -eq 0 ] then printf "%dx" $prime newnum=$((newnum/prime)) primefind $newnum 2 return else let prime++ primefind $newnum $prime fi } ############################################################################### # Main # ############################################################################### echo -n "Prime Factors of $1: primefind $num 2 printf "\b \n" # \b is used for removing last x.
OUTPUT: [root@venu ]# sh primefactors.sh Usage: scriptname <positive integer=""> [root@venu ]# sh primefactors.sh 21219797 Prime Factors of 21219797: 101x210097 [root@venu ]# sh primefactors.sh 212197 Prime Factors of 212197: 443x479 Running time of script doesn't depend on number,it depends on number of factors, more factors less time and less factors more time. [root@venu ]# time sh primefactors.sh 9999999999999999 Prime Factors of 9999999999999999: 3x3x11x17x73x101x137x5882353 real 0m1.345s user 0m1.225s sys 0m0.091s [root@venu ]# time sh primefactors.sh 999999999995 Prime Factors of 999999999995: 5x251x1831x435179 real 1m32.105s user 1m28.866s sys 0m3.192s [root@venu ]# time sh primefactors.sh 99999999000000000 Prime Factors of 99999999000000000: 2x2x2x2x2x2x2x2x2x3x3x5x5x5x5x5x5x5x5x5x11x7 3x101x137 real 0m0.543s user 0m0.508s sys 0m0.035s

9 comments:

  1. Hi Friends ,
    Prime numbers are the best way through this .Finding prime numbers can be find through it .

    ReplyDelete
  2. That's cool, I still can't figure out how the script is doing it though. :P

    ReplyDelete
  3. Just a note the factor command also does the same. This comes with the standard coreutils package.

    ReplyDelete
  4. This is rally nice article, it helped me out.

    Thank you very much.

    QuickBooks Hosting

    ReplyDelete
  5. I am getting this error while executing the above program. Is any correction needed in it?

    ~$ sh primefactors.sh 812
    primefactors.sh: 37: primefactors.sh: Syntax error: Bad for loop variable

    ReplyDelete
  6. Very nice solution
    for formate pendrive in linux
    www.cloudwalks.com

    ReplyDelete
  7. thanks for sharing
    very nice solution for me
    http://www.cloud2support.com/

    ReplyDelete
  8. thanks for sharing
    http://www.cloud2support.com/

    ReplyDelete
  9. thanks for sharing
    http://www.cloud2support.com/

    ReplyDelete