Questions tagged [factorization]

In mathematics, factorization is basically the decomposition of an object like number or polynomials into a product of smaller, simpler objects. An important subset is Integer Factorization, or further, Prime Factorization.

factorization
Filter by
Sorted by
Tagged with
0 votes
1 answer
104 views

FactorDB can't factorize number generated by getPrime

I tried to generate big prime number and minus one then trying to find divisors but it just gave the exact number. from factordb.factordb import FactorDB from Crypto.Util.number import getPrime N = ...
66 votes
16 answers
136k views

Efficiently getting all divisors of a given number

According to this post, we can get all divisors of a number through the following codes. for (int i = 1; i <= num; ++i){ if (num % i == 0) cout << i << endl; } For example,...
4 votes
2 answers
2k views

Generating all divisors of a number given its prime factorization

I want to find all divisors of numbers in range [1,107] . I know it can be solved in O(sqrt(n)). But had to run sieve of Eratosthenes before this which can be easily modified to get prime ...
8 votes
8 answers
45k views

Java Display the Prime Factorization of a number

So for my assignment, I have to write a program that asks the user for an integer input and then print out that number's prime factorization. This is what I have: import java.util.Scanner; public ...
0 votes
1 answer
83 views

But does the Fermat Factorization algorithm work?

I was testing the basic version of the Fermat Factorization method, so I'm not using any improvement whatsoever. The code I wrote in Python works as fast as expected for those numbers obtained by ...
2 votes
2 answers
518 views

Williams p+1 integer factorization

I am asked to introduce to my classmates the the Williams' p+1 algorithm to factor integers and I don't think I get it right. As far as I understand, this algorithm takes an integer N that factors ...
0 votes
1 answer
52 views

Parallelize Matrix::Cholesky() in R [closed]

I have a R code that relies on Matrix::Cholesky. I am looking for a way to use my computer's several cores. I find only theoretical research papers, not off-the-shelf packages/methods. Am I missing ...
190 votes
30 answers
275k views

What is the most efficient way of finding all the factors of a number in Python?

Can someone explain to me an efficient way of finding all the factors of a number in Python (2.7)? I can create an algorithm to do this, but I think it is poorly coded and takes too long to produce a ...
0 votes
1 answer
92 views

Prime factorization with superscript exponents java

I would like to have my outputs from my Prime Factorization module in my calculator program to be in this form: 247500 = 2² · 3² · 5⁴ · 11 instead of 2^2 * 3^2 * 5^4 * 11 or 2 2 3 3 5 5 5 5 11. The ...
39 votes
7 answers
20k views

R Function for returning ALL factors

My normal search foo is failing me. I'm trying to find an R function that returns ALL of the factors of an integer. There are at least 2 packages with factorize() functions: gmp and conf.design, ...
0 votes
0 answers
82 views

PyTorch model not learning - Loss remains unchanged

I'm currently working on a recommendation system using PyTorch and a DeepFM model architecture. Despite applying proper weight initialization and following common troubleshooting steps, I'm facing an ...
1 vote
1 answer
276 views

Algorithms for factorizing a 30 decimal digit number

My professor has given me an RSA factoring problem has assignment. The given modulus is 30 decimal digits long. I have been searching a lot about factoring algorithms. But it has been quite a headache ...
76 votes
10 answers
75k views

What is the fastest integer factorization algorithm?

I've written a program that attempts to find Amicable Pairs. This requires finding the sums of the proper divisors of numbers. Here is my current sumOfDivisors() method: int sumOfDivisors(int n) { ...
-3 votes
3 answers
105 views

Factorization: What went wrong with d? [duplicate]

Consider: Enter image description here Input: 20 17 999997 Output: 2^2 * 5 17 757 * 1321 My code: a = int(input()) # Find the factors first for i in range(2, a+1): ...
-1 votes
1 answer
158 views

How SVD works in matrix factorization [duplicate]

I want to know about the ways of factorizing a matrix using SVD (Singular Value Decomposition). I found several articles, I have gone through many of them but i am not getting a clear idea about ...
3 votes
3 answers
2k views

Can someone explain to me this part of Dixon's factorization algorithm?

I've been trying to implement Dixon's factorization method in python, and I'm a bit confused. I know that you need to give some bound B and some number N and search for numbers between sqrtN and N ...
2 votes
3 answers
157 views

Counting number of integer solutions of z³ = x²y² for given z

I have been working on this problem for some time now. The problem asks to find two numbers x and y such that the product of the squares of x and y equal the cube of k. My approach was to solve for x, ...
9 votes
5 answers
10k views

Factor a large number efficiently with gmp

I need to get all the prime factors of large numbers that can easily get to 1k bits. The numbers are practically random so it shouldn't be hard. How do I do it efficiently? I use C++ with GMP library. ...
1 vote
0 answers
361 views

Solving a symmetric banded linear system with Cholesky factorisation

I'm trying to solve a linear system Ax=b, where A has been factorised by Cholesky decomposition, and A is stored using symmetric banded storage. Given a symmetric, positive definite matrix, A, I've ...
0 votes
0 answers
65 views

Why does this factorization program fail for numbers greated than 102030405060708001?

Following is a factorization program in Python. It works fine till 102030405060708001 but produces incorrect results for greater integers. Why is this so? import math a = [] def prime(n): ...
2 votes
4 answers
364 views

Optimize a divisors algorithm in Julia?

I'm trying to write an optimized algorithm in Julia to find all divisors of an integer. The heavy part, i.e. factoring, is done using Primes.jl and the algorithm seems quite fast. But I'm thinking of ...
-1 votes
1 answer
63 views

Any useful mathematical function / algorithm to break down big numbers?

So what I want to do is breaking down numbers that are dozens of thousands big into smaller numbers, preferably 2~9. The first thing came to my mind was prime factorization, for instance the number ...
-2 votes
2 answers
46 views

go through each number between 1 and the number input until it finds a factor and adds it to a list

def factorList(num): listOfFactors = [] for i in range <= num: if num / i == 0: listOfFactors.append(i) print(listOfFactors) factorList(36) I want the ...
-3 votes
1 answer
33 views

List turns to "None", trying to make a factorizing program [duplicate]

I am trying to make a program that factorized numbers. I made a definition for making prime numbers, it worked fine, but when I try the factorization it doesn't work. I think the prime list turns to ...
0 votes
2 answers
760 views

Count number of integers in a given interval with two consecutive factors

I am trying to solve this problem which asks to find the number of integers in a given interval with consecutive factors x(x+1). 2 = 1 * 2, 6 = 2 * 3 etc., To find the count of numbers that can be ...
0 votes
1 answer
52 views

Change lib's sources depending on conditional requirements in a factorized way using boost build/b2/bjam

I have a lib target that needs different (additional) libraries on some OSes. I would like to do something like: lib MyLib : $(SOURCES) $(COMMON_LIBS) <target-os>windows:$(WINDOWS_LIBS) ; but ...
19 votes
3 answers
4k views

what is the algorithm behind the factor command in linux?

The factor command prints the prime factors of specified integer NUMBER. When I tried it factor 12345678912345678912 even for such big numbers, it results within milliseconds. Which algorithm is it ...
-1 votes
3 answers
236 views

How can I avoid using too much if statements / refactor this method?

It looks horrible, but I don't see how can I factorize that ? I thought of creating small boolean methods but I think it won't change too much, there will always be as many ifs ? private String ...
1 vote
1 answer
82 views

Trouble finding the smallest number of 1's required to represent an integer

I'm doing some programming challenges for fun and I've gotten really stuck on one particular problem regarding how to represent integers using only ones. The question is what is the least number of ...
1 vote
2 answers
5k views

Pollard Rho factorization method implementation in C

Can anyone help me out with the pollard rho implementation? I have implemented this in C. It's working fine for numbers upto 10 digits but it's not able to handle greater numbers. Please help me out ...
2 votes
3 answers
10k views

Factor a quadratic polynomial in Python

Since factoring a quadratic equation in my head just happens, and has done that since I learned it - how would I go about starting to write a quadratic factorer in Python?
3 votes
6 answers
2k views

Factorization of large numbers

In class we found this programming problem, and currently, we have no idea how to solve it. The positive integer n is given. It is known that n = p * q, where p and q are primes, p<=q and |q-k*p|...
3 votes
3 answers
3k views

Pollard rho integer factorization

I am trying to implement Pollard Rho integer factorization in C/C++.Google gives me a Java implementation of the problem here. I don't know Java that well,so what I came up with this.My implemenation ...
3 votes
3 answers
2k views

Pollard Rho factorization method implementation

Every time I factor a number using Pollard Rho factorization method is it necessary to check for its primality before Pollard Rho factorization ? If yes then I have to implement Miller Rabin's ...
-1 votes
2 answers
74 views

Why is the Python Code running so long and is there any way to get the output quickly?

I have a Python Code to get the largest prime factor of a Number and the below is my code When I give the input to the number up to an 8-digit number takes a few minutes but when I tried running the ...
0 votes
1 answer
183 views

Sagemath: Factoring an integer inside a ring of integers different from $\mathbb{Z}$

I am trying to find divisors of an element in the ring of integers of a Cyclotomic Field. My code is K=CyclotomicField(23) L=K.ring_of_integers() L.factor(2) It gives an error: '...
0 votes
1 answer
59 views

How to factor powers of an matrix in a equation in Sympy?

I have an expression that comes from from sympy.physics.quantum import Commutator as cmm x, t, A, V, W, D = sp.symbols('x t A V W D', commutative = False) Q = sp.Function('Q', commutative = ...
0 votes
0 answers
55 views

Improving a clumsy automatic cuboid domain decomposition algorithm

Introduction For my library, I need to split up a cuboid point lattice for assignment to multiple processing elements (PEs). As you can see, no points are shared between the PEs, and certain PEs (...
1 vote
1 answer
123 views

Reusing symbolic factorization for sparse non-PSD matrix in matlab

I want to solve a large sparse matrix equation Ax=b in MATLAB many times, where A has the same sparsity pattern but different values each time. A is not positive definite but symmetric here. The ...
23 votes
8 answers
12k views

Efficient storage of prime numbers

For a library, I need to store the first primes numbers up to a limit L. This collection must have a O(1) lookup time (to check whether a number is prime or not) and it must be easy, given a number, ...
1 vote
1 answer
70 views

Heap Corruption while getting LU factorization's nxn matrix

im trying to make LU factorization on n x n(getting n from scanf) matrix HEAP CORRUPTION causes when i try to make n x n matrix and put numbers in :/ i dont know where to fix as i am using malloc for ...
1 vote
1 answer
67 views

Improve/fix prime factorization function

I have a function prime factorization, but it works wierdly and I have no idea how to make it right. It's expected to print factors through 'x' and write like 2^(power) or 3^(power) if 2's or 3's are ...
3 votes
2 answers
876 views

Checking if a number can be written as a product of some fibonacci numbers

I have tried to solve the problem above but I got stuck. I guess that it all comes to factorization by non-prime numbers. The number could be really big - about 10^15. What I attempted to do is to ...
3 votes
2 answers
5k views

Most efficient way to find all factors with GMPY2 (or GMP)?

I know there's already a question similar to this, but I want to speed it up using GMPY2 (or something similar with GMP). Here is my current code, it's decent but can it be better? Edit: new code, ...
0 votes
2 answers
34 views

how to represent multiplicty of prime factor in factorization in python

I code this function factorization(n)... like below def factorization(n): factor=[] for i in range(2,n+1): while n % i == 0: n = n/i factor.append(i) ...
0 votes
1 answer
341 views

How to calculate the number of divisors in a list for a number in scheme

How to I create a function called numDivisors. The function is defined as (numDivisors n listOfNums) and it counts the number of integers in the list that divide n without any remainder. Example of ...
0 votes
0 answers
25 views

Error in factor_list with polynomial containing complex exponentials

I want to make a factor list out an expressions and found a weird behaviour in a special case, which I do not understand. One example would be: The polynomial contains a pre-factor of exp(-4piI/7) and ...
2 votes
0 answers
181 views

I think I found another algorithm for number factorization [closed]

A few days ago i thought a new algorithm (maybe it is just new for me and it has already been developed ) of number factorization My main idea is like that: For example lets say we want to find ...
0 votes
0 answers
109 views

Factorizing multivariate polynomial over finite fields

I'm working on a project where I need to factorize a given bivariate polynomial over a finite field, is there any python library that can help me? Sympy cannot factorize multivariate polynomial over a ...
0 votes
2 answers
258 views

How to make this Haskell program run faster

So I've been trying to learn Haskell by solving some problems on Codeforce. And I am getting a lot of TLE (Time Limit Exceed) even though I think my time complexity is optimal. My question is: is the ...

1
2 3 4 5 6