Input an Integer and get its prime factors and duplicates

Question

Possible Duplicate:
Prime Factors In C#

I am trying to get this coding to give me all the prime factors of the integer that is inputted, including its duplicates. I have this current code and it seems to be working sort of but it isn't showing all of it's prime factors and duplicates. Any help would be appreciated.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace _1_Numeric_Problem
{
    class Program
    {
        static void Main(string[] args)
        {
            string myInput;
            int myInt;
            int p;

            Console.WriteLine(("Please input an integer"));

            myInput = Console.ReadLine();
            myInt = Int32.Parse(myInput);

            {
                for (int i = 2; i > 1; i++)
                {
                    if (i == 100000)

                        break;

                    if (myInt % i == 0)
                    {

                        if (i <= 3)
                        {

                            Console.Write("{0} ", i);
                            Console.ReadLine();
                            continue;
                        }

                        else
                        {
                            for (p = 2; p < i; p++)
                                if (i % p != 0)
                                {
                                    Console.Write("{0} ", i);
                                    Console.ReadLine();
                                    return;
                                    Console.ReadLine();
                                }
                                else
                                {
                                    p++;
                                    continue;
                                }

                        }
                    }
                }
            }
        }
    }
}

Please edit your sample so it does no mix reading/writing with computing results. And possibly remove input altogether as it is unrelated to the question. And add actual question ... — Alexei Levenkov, Nov 07 '12 at 17:46

score 2 · Answer 1 · edited Nov 07 '12 at 18:35

Try replacing the following code:

for (p = 2; p < i; p++) {
    if (i % p != 0) {
        Console.Write("{0} ", i);
        Console.ReadLine();
        return;
        Console.ReadLine();
    } else {
        p++;
        continue;
    }
}

With this instead:

bool isPrime = true;

for (p = 2; p <= Math.Sqrt(i); p++) {
    if (i % p == 0) {
        isPrime = false;
        break;
    }

    if (isPrime) {
        Console.Write("{0} ", i);
        Console.ReadLine();
    }
}

BBB · Answer 2 · 2012-11-07T17:51:19.607

1

Can't you just make a for loop like this?

for (int i = 2; i < myInt; i++)
{
    if(myInt % i == 0)
        //Do something with it.
}

edited Nov 07 '12 at 17:51

answered Nov 07 '12 at 17:43

BBB

615
3
12
26

score 1 · Answer 3 · answered Nov 07 '12 at 18:26

The basic algorithm for integer factorization using trial division tries each potential factor starting from 2, and if it divides n, outputs the factor, reduces n, and searches for the next factor; note that f is not incremented if it divides n, since it might again divide the reduced n. The loop stops when f is greater than the square root of n, since at that point n must be prime. Here's the pseudocode:

function factors(n)
    f := 2
    while f * f <= n
        if n % f == 0
            output f
            n := n / f
        else
            f := f + 1
    output n

There are better ways to factor integers, but that should get you started. When you're ready for more, I modestly recommend this essay on my blog.

Input an Integer and get its prime factors and duplicates

3 Answers3