• 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
26 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

26 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. No sort, but reversing a [linked list]

    #include
    #include

    #define MAX 10 /* max of 10 elements */

    struct lnode {
    int number;
    struct lnode *next;
    };

    /* add a lnode at the beginning of the list */
    void llist_add_begin(struct lnode **n, int val);
    /* reverse the whole list */
    void llist_reverse(struct lnode **n);
    /* display the whole linked list */
    void llist_display(struct lnode *n);

    int main(void) {
    struct lnode *new = NULL;
    int i = 0;

    /* insert some numbers */
    for(i = 0; i <= MAX; i++)
    llist_add_begin(&new, i);

    printf("linked list before reversal:");
    llist_display(new);
    llist_reverse(&new);
    printf("linked list after reversal:");
    llist_display(new);

    return 0;
    }

    /* add a lnode at the beginning of the list */
    void llist_add_begin(struct lnode **n, int val) {
    struct lnode *temp = NULL;

    /* add new node */
    temp = malloc(sizeof(struct lnode));
    temp->number = val;
    temp->next = *n;
    *n = temp;
    }

    /* reverse the whole list */
    void llist_reverse(struct lnode **n) {
    struct lnode *a = NULL;
    struct lnode *b = NULL;
    struct lnode *c = NULL;
    a = *n, b = NULL;

    while(a != NULL) {
    c = b, b = a, a = a->next;
    b->next = c;
    }

    *n = b;
    }

    /* display the whole linked list */
    void llist_display(struct lnode *n) {
    while(n != NULL)
    printf(" %d", n->number), n = n->next;

    printf("\n");
    }

    ReplyDelete
  10. Well post its tell us theory od number and also tell us how to make a file thanks for share it professional editing services .

    ReplyDelete

  11. What an awesome post, I just read it from start to end. Learned something new after a long time.


    SAP MM training in Chennai

    ReplyDelete
  12. Hey, thanks a lot for sharing. There is another article I would want to share with you. http://resumewriter-s.com/ If you feel like, you can always look through the whole blog, there are many posts on different topics, which might be pretty much to your liking.

    ReplyDelete
  13. JSON Converter, Formatter, Validator & Editor Online is a web-based tool to view, edit, validate and format JSON which shows your data side by side in a clear, editable treeview and in a code editor.
    json converter

    ReplyDelete
  14. Your article reflects the issue people are concerned about. The article provides timely information that reflects multi-dimensional views from multiple perspectives. I look forward to reading quality articles that contain timely information from you.

    ReplyDelete
  15. That's cool, I still can't figure out how the script is doing it though. :P
    Try to play happy room game now.

    ReplyDelete
  16. Interesting article! Thank you for sharing them! I hope you will continue to have similar posts to share with everyone!

    ReplyDelete
  17. What's up every one, here every person is sharing these kinds of familiarity, thus it's nice to read this webpage, and I used to pay a quick visit this website all the time. msn hotmail sign in

    ReplyDelete
  18. A great initiative, it is worth doing such things.

    ReplyDelete
  19. Incredibly you describe it, it is very nice to read it.

    ReplyDelete
  20. Awesome post. Appreciate your efforts and really enjoyed the style of your writing.

    ReplyDelete
  21. Wow, Excellent post. This article is really very interesting and effective

    PHP Training in Chennai
    PHP Training

    ReplyDelete