|
Thread Rules
1. This is not a "do my homework for me" thread. If you have specific questions, ask, but don't post an assignment or homework problem and expect an exact solution.
2. No recruiting for your cockamamie projects (you won't replace facebook with 3 dudes you found on the internet and $20)
3. If you can't articulate why a language is bad, don't start slinging shit about it. Just remember that nothing is worse than making CSS IE6 compatible.
4. Use [code] tags to format code blocks. |
Hyrule19030 Posts
$sql = "INSERT INTO test VALUES(?);";
$sql = $sql . $sql . $sql;
might work...I use my own wrapper though so I haven't actually tried this.
|
On August 30 2012 04:21 tofucake wrote:
$sql = "INSERT INTO test VALUES(?);";
$sql = $sql . $sql . $sql;
might work...I use my own wrapper though so I haven't actually tried this.
That would result in
$sql = "INSERT INTO test VALUES(?);INSERT INTO test VALUES(?);INSERT INTO test VALUES(?);";
To then bind this with
$stmt -> bind_param("sss", $value[0],$value[1],$value[2]);
becomes extremely messy, especially since the length of the array varies, or did I misunderstand you? Don't know if this is faster.
|
On August 30 2012 04:17 nakam wrote:Show nested quote +On August 30 2012 03:58 tofucake wrote:$sql = "INSERT INTO test VALUES(?, ?, ?)";
$values = array('one', 'two', 'three');
if($stmt = $db -> prepare($sql)) $stmt->execute($values); Well that's if I wanted to insert the values in different columns. I want to insert multiple rows.
which DB library?
In PDO you can simply use named parameters:
$sql = "INSERT INTO test VALUES (:a, :b, :c)";
$sth = $dbh->prepare($sql);
foreach ($values as $value)
{
$sth->execute(array(
":a" => $value['a'],
":b" => $value['b'],
...
));
}
|
Hyrule19030 Posts
|
On August 30 2012 05:24 Morfildur wrote:Show nested quote +On August 30 2012 04:17 nakam wrote:On August 30 2012 03:58 tofucake wrote:$sql = "INSERT INTO test VALUES(?, ?, ?)";
$values = array('one', 'two', 'three');
if($stmt = $db -> prepare($sql)) $stmt->execute($values); Well that's if I wanted to insert the values in different columns. I want to insert multiple rows. which DB library? In PDO you can simply use named parameters:
$sql = "INSERT INTO test VALUES (:a, :b, :c)";
$sth = $dbh->prepare($sql);
foreach ($values as $value)
{
$sth->execute(array(
":a" => $value['a'],
":b" => $value['b'],
...
));
}
MySQLi unfortunately.
|
On August 29 2012 15:43 Blisse wrote:Show nested quote +On August 29 2012 15:21 frogmelter wrote:On August 29 2012 14:53 Blisse wrote:On August 29 2012 14:49 frogmelter wrote:
For an assignment at school, I'm supposed to read in a number and find all the factors and bold the ones that are prime.
This is incredibly simple, except my professor put in
9223372036854775805
9223372036854775806
9223372036854775807
as some of the inputs that we need to test. This obviously takes a super long time to compute. I'm stumped on how I would optimize my code enough so that it would run quickly.
I can think of a clever way to get it to display all the factors, but not to calculate which ones are prime, especially for such a huge number. Can anyone give me some ideas? That's a very... interesting assignment, at least the way it's worded. By my gut, if you get the prime factorization, from there you can calculate all unique permutations of those that get you something less than the inputted number, which simply gives you all the factors of the number. Since you have the prime factorization, you should have all the primes you need. In my mind though, that seems like it'll take a very long time, but it might not! Seems like he just wants you to implement a very good prime factorization method. You'll have to make a call on whether you want to make one yourself or just follow the really optimized ones online. Calculating all the prime factors is no good, since I need to calculate all the factors as well. This is what I have so far. + Show Spoiler +
public void calcPrime()
{
if (value==2)
{
setPrime(true);
return;
}
if (value%3==0)
{
setPrime(false);
return;
}
if (value%10==5)
{
setPrime(false);
return;
}
if (value%2==0)
{
setPrime(false);
return;
}
if (value==1)
{
setPrime(false);
return;
}
for(long l=3; true; l++)
{
long square = l * l;
if (square > getValue())
{
break;
}
l = getNextTestPrime(l, square);
if (l == -1l)
{
setPrime(false);
return;
}
if(value%l==0)
{
setPrime(false);
return;
}
}
setPrime(true);
}
private Long getNextTestPrime(long l, long square)
{
while (l<square)
{
l=l+2;
if (!(l%3==0||l%5==0))
{
return l;
}
}
return (long) -1;
}
This will only test the numbers that are odd and are not divisible by 3 or end in 5 [the ones that end in 0 are caught by the mod 2 case] That's about as optimizes as I think I can get. Still no good on the 9 * 10^20 number so far. Hey, yup, I see what you're going for here, but I think you misunderstood my idea. I'm not in Computer Science, so I don't remember the proof or theorem by heart, but I took a course on proofs which included prime factorization. Which stated something like, given N = (f1)^(k1) * (f2)^(k2) * ... * (fn)^(kn), where f1, f2 ... fn are all primes, all possible factors can be determined by choosing different exponents, qm, such that 0 <= qm <= km, for 1 <= m <= n. I'll give an example since that's not super clear. + Show Spoiler +
Given 144 = 2^4 * 3^2 is the prime factorization. 2 and 3 are the ONLY prime factors, since that's what the prime factorization gives you.
From there, you have 2, with exponents from 0 to 4, and 3, with exponents from 0 to 2.
So all the factors are,
2^0 * 3^0 = 1
2^1 * 3^0 = 2
2^2 * 3^0 = 4
2^3 * 3^0 = 8
2^4 * 3^0 = 16
2^0 * 3^1 = 3
2^1 * 3^1 = 6
2^2 * 3^1 = 12
2^3 * 3^1 = 24
2^4 * 3^1 = 48
2^0 * 3^2 = 9
2^1 * 3^2 = 18
2^2 * 3^2 = 36
2^3 * 3^2 = 72
2^4 * 3^2 = 144
Hope that's a bit clearer. 1. Find the prime factorization. 2. Use the above method/theorem to calculate all the permutations, which gives you all the factors. By breaking the problem into parts, it should be a lot less complicated, no? I wish I remembered the name of the theorem to make it clearer for you. Best of luck.
Well, I've written code to find all the prime factors.
So I have a list of something like 2^2 * 3^2 * 5^2 * 7^2
However, I'm stumped on how I would multiply everything to get the actual factors.
For example, the number 44100 is
2^2 * 3^2 * 5^2 * 7^2
I would have to multiply everything by each other
ie.
2^1 * 3^1
2^1 * 3^2
2^1 * 3^1 * 5^1
2^1 * 3^1 * 5^2
2^1 * 3^1 * 7^1
2^1 * 3^1 * 7^2
2^1 * 3^1 * 5^1 * 7^1
2^1 * 3^1 * 5^1 * 7^2
2^2 * 3^1
2^2 * 3^2
2^2 * 3^1 * 5^1
2^2 * 3^1 * 5^2
2^2 * 3^1 * 7^1
2^2 * 3^1 * 7^2
2^2 * 3^1 * 5^1 * 7^1
2^2 * 3^1 * 5^1 * 7^2
I don't know how I would go about that, since there is a variable number of prime factors [If I chose 900, then it would only be 2^2 * 3^2 * 5^2]. If the number of prime factors were constant, it would be really simple
I don't know how I would calculate it so that it multiplies every permutation. Especially since sometimes I would have to skip middle values ie.
2^2 * 3^0 * 5^2 * 7^0 * 11^2
This seems like some sort of recursion that I need to do perhaps... Any ideas are greatly appreciated
|
On August 30 2012 05:46 nakam wrote:Show nested quote +On August 30 2012 05:24 Morfildur wrote:On August 30 2012 04:17 nakam wrote:On August 30 2012 03:58 tofucake wrote:$sql = "INSERT INTO test VALUES(?, ?, ?)";
$values = array('one', 'two', 'three');
if($stmt = $db -> prepare($sql)) $stmt->execute($values); Well that's if I wanted to insert the values in different columns. I want to insert multiple rows. which DB library? In PDO you can simply use named parameters:
$sql = "INSERT INTO test VALUES (:a, :b, :c)";
$sth = $dbh->prepare($sql);
foreach ($values as $value)
{
$sth->execute(array(
":a" => $value['a'],
":b" => $value['b'],
...
));
}
MySQLi unfortunately.
if I am not mistaken, woudln't you insert multiple rows like?
$sql = "insert into test (fielda, fieldb, fieldc) values (a1, a2, a3) (b1, b2, b3) (c1,c2,c3)"
so with an array... (assuming php and 'one' 'two' 'three' each get their seperate row...)
$sql = "insert into test (columnName) values ";
for ($i=0;$i<count($array);$i++) {
$sql .= "(".$array[$i].")";
}
$query = mysql_query($sql) or die(mysql_error());
EDIT: There would be a comma delimiter:
so $string .= ",(".$array[$i].")";
and then say $sql .= substr($string,1);
(This will remove the first comma)
|
I didn't spend too much time thinking whether the following is the best way of producing all the possible products but at least consider it food for thought!
Let's say you have a prime factorization, each prime with some exponent. Now consider that you drop the exponents and instead have a list of prime factors and the number of times a prime is in the list is based on the exponent.
So if you have a prime factorization 2^2 * 3^2 * 5^2 * 7^2 consider it as a list 22335577.
Now if you want to list the products of each different subset of this list you can do the following:
Start with an empty list L
For each member N in the list of primes
Multiply each member of L with N and add the new numbers you get to L if they are not already there
add N to L if it is not already there
end
And in the end L will include all the divisors of your original number (other than 1)
Now obviously you don't need to produce this list but instead if you have the primes and their exponents you can just loop for each separate prime from 1 to the exponent to achieve the same goal but I thought this was more illustrative.
|
On August 30 2012 15:51 frogmelter wrote:Show nested quote +On August 29 2012 15:43 Blisse wrote:On August 29 2012 15:21 frogmelter wrote:On August 29 2012 14:53 Blisse wrote:On August 29 2012 14:49 frogmelter wrote:
For an assignment at school, I'm supposed to read in a number and find all the factors and bold the ones that are prime.
This is incredibly simple, except my professor put in
9223372036854775805
9223372036854775806
9223372036854775807
as some of the inputs that we need to test. This obviously takes a super long time to compute. I'm stumped on how I would optimize my code enough so that it would run quickly.
I can think of a clever way to get it to display all the factors, but not to calculate which ones are prime, especially for such a huge number. Can anyone give me some ideas? That's a very... interesting assignment, at least the way it's worded. By my gut, if you get the prime factorization, from there you can calculate all unique permutations of those that get you something less than the inputted number, which simply gives you all the factors of the number. Since you have the prime factorization, you should have all the primes you need. In my mind though, that seems like it'll take a very long time, but it might not! Seems like he just wants you to implement a very good prime factorization method. You'll have to make a call on whether you want to make one yourself or just follow the really optimized ones online. Calculating all the prime factors is no good, since I need to calculate all the factors as well. This is what I have so far. + Show Spoiler +
public void calcPrime()
{
if (value==2)
{
setPrime(true);
return;
}
if (value%3==0)
{
setPrime(false);
return;
}
if (value%10==5)
{
setPrime(false);
return;
}
if (value%2==0)
{
setPrime(false);
return;
}
if (value==1)
{
setPrime(false);
return;
}
for(long l=3; true; l++)
{
long square = l * l;
if (square > getValue())
{
break;
}
l = getNextTestPrime(l, square);
if (l == -1l)
{
setPrime(false);
return;
}
if(value%l==0)
{
setPrime(false);
return;
}
}
setPrime(true);
}
private Long getNextTestPrime(long l, long square)
{
while (l<square)
{
l=l+2;
if (!(l%3==0||l%5==0))
{
return l;
}
}
return (long) -1;
}
This will only test the numbers that are odd and are not divisible by 3 or end in 5 [the ones that end in 0 are caught by the mod 2 case] That's about as optimizes as I think I can get. Still no good on the 9 * 10^20 number so far. Hey, yup, I see what you're going for here, but I think you misunderstood my idea. I'm not in Computer Science, so I don't remember the proof or theorem by heart, but I took a course on proofs which included prime factorization. Which stated something like, given N = (f1)^(k1) * (f2)^(k2) * ... * (fn)^(kn), where f1, f2 ... fn are all primes, all possible factors can be determined by choosing different exponents, qm, such that 0 <= qm <= km, for 1 <= m <= n. I'll give an example since that's not super clear. + Show Spoiler +
Given 144 = 2^4 * 3^2 is the prime factorization. 2 and 3 are the ONLY prime factors, since that's what the prime factorization gives you.
From there, you have 2, with exponents from 0 to 4, and 3, with exponents from 0 to 2.
So all the factors are,
2^0 * 3^0 = 1
2^1 * 3^0 = 2
2^2 * 3^0 = 4
2^3 * 3^0 = 8
2^4 * 3^0 = 16
2^0 * 3^1 = 3
2^1 * 3^1 = 6
2^2 * 3^1 = 12
2^3 * 3^1 = 24
2^4 * 3^1 = 48
2^0 * 3^2 = 9
2^1 * 3^2 = 18
2^2 * 3^2 = 36
2^3 * 3^2 = 72
2^4 * 3^2 = 144
Hope that's a bit clearer. 1. Find the prime factorization. 2. Use the above method/theorem to calculate all the permutations, which gives you all the factors. By breaking the problem into parts, it should be a lot less complicated, no? I wish I remembered the name of the theorem to make it clearer for you. Best of luck. Well, I've written code to find all the prime factors. So I have a list of something like 2^2 * 3^2 * 5^2 * 7^2 However, I'm stumped on how I would multiply everything to get the actual factors. For example, the number 44100 is 2^2 * 3^2 * 5^2 * 7^2 I would have to multiply everything by each other ie. 2^1 * 3^1 2^1 * 3^2 2^1 * 3^1 * 5^1 2^1 * 3^1 * 5^2 2^1 * 3^1 * 7^1 2^1 * 3^1 * 7^2 2^1 * 3^1 * 5^1 * 7^1 2^1 * 3^1 * 5^1 * 7^2 2^2 * 3^1 2^2 * 3^2 2^2 * 3^1 * 5^1 2^2 * 3^1 * 5^2 2^2 * 3^1 * 7^1 2^2 * 3^1 * 7^2 2^2 * 3^1 * 5^1 * 7^1 2^2 * 3^1 * 5^1 * 7^2 I don't know how I would go about that, since there is a variable number of prime factors [If I chose 900, then it would only be 2^2 * 3^2 * 5^2]. If the number of prime factors were constant, it would be really simple I don't know how I would calculate it so that it multiplies every permutation. Especially since sometimes I would have to skip middle values ie. 2^2 * 3^0 * 5^2 * 7^0 * 11^2 This seems like some sort of recursion that I need to do perhaps... Any ideas are greatly appreciated
Yes it is a recursion. Here is a python solution. I didn't completely test but the results look about right at a glance).
def factors_from_prime_factors(prime_factors):
if not prime_factors:
return []
else:
factors = factors_from_prime_factors(prime_factors[1:])
factors = prime_factors + map(lambda x: x*prime_factors[0], factors)
factors = list(set(factors))
factors.sort()
return factors
The prime factors must be given as a list like [2, 2, 3, 3, 5, 5, 7, 7] in the 44100 case.
>>> factors_from_prime_factors([2, 2, 3, 3, 5, 5, 7, 7])
[2, 3, 4, 5, 6, 7, 10, 12, 14, 20, 28, 36, 60, 84, 180, 252, 900, 1260, 6300, 44100]
edit: sorting can be taken out or done outside the function, same with the conversion to a set (it just removes duplicates), but I just put them in one function for simplicity and to look nice
|
On August 30 2012 15:51 frogmelter wrote:Show nested quote +On August 29 2012 15:43 Blisse wrote:On August 29 2012 15:21 frogmelter wrote:On August 29 2012 14:53 Blisse wrote:On August 29 2012 14:49 frogmelter wrote:
For an assignment at school, I'm supposed to read in a number and find all the factors and bold the ones that are prime.
This is incredibly simple, except my professor put in
9223372036854775805
9223372036854775806
9223372036854775807
as some of the inputs that we need to test. This obviously takes a super long time to compute. I'm stumped on how I would optimize my code enough so that it would run quickly.
I can think of a clever way to get it to display all the factors, but not to calculate which ones are prime, especially for such a huge number. Can anyone give me some ideas? That's a very... interesting assignment, at least the way it's worded. By my gut, if you get the prime factorization, from there you can calculate all unique permutations of those that get you something less than the inputted number, which simply gives you all the factors of the number. Since you have the prime factorization, you should have all the primes you need. In my mind though, that seems like it'll take a very long time, but it might not! Seems like he just wants you to implement a very good prime factorization method. You'll have to make a call on whether you want to make one yourself or just follow the really optimized ones online. Calculating all the prime factors is no good, since I need to calculate all the factors as well. This is what I have so far. + Show Spoiler +
public void calcPrime()
{
if (value==2)
{
setPrime(true);
return;
}
if (value%3==0)
{
setPrime(false);
return;
}
if (value%10==5)
{
setPrime(false);
return;
}
if (value%2==0)
{
setPrime(false);
return;
}
if (value==1)
{
setPrime(false);
return;
}
for(long l=3; true; l++)
{
long square = l * l;
if (square > getValue())
{
break;
}
l = getNextTestPrime(l, square);
if (l == -1l)
{
setPrime(false);
return;
}
if(value%l==0)
{
setPrime(false);
return;
}
}
setPrime(true);
}
private Long getNextTestPrime(long l, long square)
{
while (l<square)
{
l=l+2;
if (!(l%3==0||l%5==0))
{
return l;
}
}
return (long) -1;
}
This will only test the numbers that are odd and are not divisible by 3 or end in 5 [the ones that end in 0 are caught by the mod 2 case] That's about as optimizes as I think I can get. Still no good on the 9 * 10^20 number so far. Hey, yup, I see what you're going for here, but I think you misunderstood my idea. I'm not in Computer Science, so I don't remember the proof or theorem by heart, but I took a course on proofs which included prime factorization. Which stated something like, given N = (f1)^(k1) * (f2)^(k2) * ... * (fn)^(kn), where f1, f2 ... fn are all primes, all possible factors can be determined by choosing different exponents, qm, such that 0 <= qm <= km, for 1 <= m <= n. I'll give an example since that's not super clear. + Show Spoiler +
Given 144 = 2^4 * 3^2 is the prime factorization. 2 and 3 are the ONLY prime factors, since that's what the prime factorization gives you.
From there, you have 2, with exponents from 0 to 4, and 3, with exponents from 0 to 2.
So all the factors are,
2^0 * 3^0 = 1
2^1 * 3^0 = 2
2^2 * 3^0 = 4
2^3 * 3^0 = 8
2^4 * 3^0 = 16
2^0 * 3^1 = 3
2^1 * 3^1 = 6
2^2 * 3^1 = 12
2^3 * 3^1 = 24
2^4 * 3^1 = 48
2^0 * 3^2 = 9
2^1 * 3^2 = 18
2^2 * 3^2 = 36
2^3 * 3^2 = 72
2^4 * 3^2 = 144
Hope that's a bit clearer. 1. Find the prime factorization. 2. Use the above method/theorem to calculate all the permutations, which gives you all the factors. By breaking the problem into parts, it should be a lot less complicated, no? I wish I remembered the name of the theorem to make it clearer for you. Best of luck. Well, I've written code to find all the prime factors. So I have a list of something like 2^2 * 3^2 * 5^2 * 7^2 However, I'm stumped on how I would multiply everything to get the actual factors. For example, the number 44100 is 2^2 * 3^2 * 5^2 * 7^2 I would have to multiply everything by each other ie. 2^1 * 3^1 2^1 * 3^2 2^1 * 3^1 * 5^1 2^1 * 3^1 * 5^2 2^1 * 3^1 * 7^1 2^1 * 3^1 * 7^2 2^1 * 3^1 * 5^1 * 7^1 2^1 * 3^1 * 5^1 * 7^2 2^2 * 3^1 2^2 * 3^2 2^2 * 3^1 * 5^1 2^2 * 3^1 * 5^2 2^2 * 3^1 * 7^1 2^2 * 3^1 * 7^2 2^2 * 3^1 * 5^1 * 7^1 2^2 * 3^1 * 5^1 * 7^2 I don't know how I would go about that, since there is a variable number of prime factors [If I chose 900, then it would only be 2^2 * 3^2 * 5^2]. If the number of prime factors were constant, it would be really simple I don't know how I would calculate it so that it multiplies every permutation. Especially since sometimes I would have to skip middle values ie. 2^2 * 3^0 * 5^2 * 7^0 * 11^2 This seems like some sort of recursion that I need to do perhaps... Any ideas are greatly appreciated
Google Miller Rabin. It will take you maybe an hour to do and is way simpler.
|
On August 31 2012 05:34 zzdd wrote:Show nested quote +On August 30 2012 15:51 frogmelter wrote:On August 29 2012 15:43 Blisse wrote:On August 29 2012 15:21 frogmelter wrote:On August 29 2012 14:53 Blisse wrote:On August 29 2012 14:49 frogmelter wrote:
For an assignment at school, I'm supposed to read in a number and find all the factors and bold the ones that are prime.
This is incredibly simple, except my professor put in
9223372036854775805
9223372036854775806
9223372036854775807
as some of the inputs that we need to test. This obviously takes a super long time to compute. I'm stumped on how I would optimize my code enough so that it would run quickly.
I can think of a clever way to get it to display all the factors, but not to calculate which ones are prime, especially for such a huge number. Can anyone give me some ideas? That's a very... interesting assignment, at least the way it's worded. By my gut, if you get the prime factorization, from there you can calculate all unique permutations of those that get you something less than the inputted number, which simply gives you all the factors of the number. Since you have the prime factorization, you should have all the primes you need. In my mind though, that seems like it'll take a very long time, but it might not! Seems like he just wants you to implement a very good prime factorization method. You'll have to make a call on whether you want to make one yourself or just follow the really optimized ones online. Calculating all the prime factors is no good, since I need to calculate all the factors as well. This is what I have so far. + Show Spoiler +
public void calcPrime()
{
if (value==2)
{
setPrime(true);
return;
}
if (value%3==0)
{
setPrime(false);
return;
}
if (value%10==5)
{
setPrime(false);
return;
}
if (value%2==0)
{
setPrime(false);
return;
}
if (value==1)
{
setPrime(false);
return;
}
for(long l=3; true; l++)
{
long square = l * l;
if (square > getValue())
{
break;
}
l = getNextTestPrime(l, square);
if (l == -1l)
{
setPrime(false);
return;
}
if(value%l==0)
{
setPrime(false);
return;
}
}
setPrime(true);
}
private Long getNextTestPrime(long l, long square)
{
while (l<square)
{
l=l+2;
if (!(l%3==0||l%5==0))
{
return l;
}
}
return (long) -1;
}
This will only test the numbers that are odd and are not divisible by 3 or end in 5 [the ones that end in 0 are caught by the mod 2 case] That's about as optimizes as I think I can get. Still no good on the 9 * 10^20 number so far. Hey, yup, I see what you're going for here, but I think you misunderstood my idea. I'm not in Computer Science, so I don't remember the proof or theorem by heart, but I took a course on proofs which included prime factorization. Which stated something like, given N = (f1)^(k1) * (f2)^(k2) * ... * (fn)^(kn), where f1, f2 ... fn are all primes, all possible factors can be determined by choosing different exponents, qm, such that 0 <= qm <= km, for 1 <= m <= n. I'll give an example since that's not super clear. + Show Spoiler +
Given 144 = 2^4 * 3^2 is the prime factorization. 2 and 3 are the ONLY prime factors, since that's what the prime factorization gives you.
From there, you have 2, with exponents from 0 to 4, and 3, with exponents from 0 to 2.
So all the factors are,
2^0 * 3^0 = 1
2^1 * 3^0 = 2
2^2 * 3^0 = 4
2^3 * 3^0 = 8
2^4 * 3^0 = 16
2^0 * 3^1 = 3
2^1 * 3^1 = 6
2^2 * 3^1 = 12
2^3 * 3^1 = 24
2^4 * 3^1 = 48
2^0 * 3^2 = 9
2^1 * 3^2 = 18
2^2 * 3^2 = 36
2^3 * 3^2 = 72
2^4 * 3^2 = 144
Hope that's a bit clearer. 1. Find the prime factorization. 2. Use the above method/theorem to calculate all the permutations, which gives you all the factors. By breaking the problem into parts, it should be a lot less complicated, no? I wish I remembered the name of the theorem to make it clearer for you. Best of luck. Well, I've written code to find all the prime factors. So I have a list of something like 2^2 * 3^2 * 5^2 * 7^2 However, I'm stumped on how I would multiply everything to get the actual factors. For example, the number 44100 is 2^2 * 3^2 * 5^2 * 7^2 I would have to multiply everything by each other ie. 2^1 * 3^1 2^1 * 3^2 2^1 * 3^1 * 5^1 2^1 * 3^1 * 5^2 2^1 * 3^1 * 7^1 2^1 * 3^1 * 7^2 2^1 * 3^1 * 5^1 * 7^1 2^1 * 3^1 * 5^1 * 7^2 2^2 * 3^1 2^2 * 3^2 2^2 * 3^1 * 5^1 2^2 * 3^1 * 5^2 2^2 * 3^1 * 7^1 2^2 * 3^1 * 7^2 2^2 * 3^1 * 5^1 * 7^1 2^2 * 3^1 * 5^1 * 7^2 I don't know how I would go about that, since there is a variable number of prime factors [If I chose 900, then it would only be 2^2 * 3^2 * 5^2]. If the number of prime factors were constant, it would be really simple I don't know how I would calculate it so that it multiplies every permutation. Especially since sometimes I would have to skip middle values ie. 2^2 * 3^0 * 5^2 * 7^0 * 11^2 This seems like some sort of recursion that I need to do perhaps... Any ideas are greatly appreciated Google Miller Rabin. It will take you maybe an hour to do and is way simpler.
He said he already figured out how to find the prime factors ...
|
On August 30 2012 17:48 spudde123 wrote:
I didn't spend too much time thinking whether the following is the best way of producing all the possible products but at least consider it food for thought!
Let's say you have a prime factorization, each prime with some exponent. Now consider that you drop the exponents and instead have a list of prime factors and the number of times a prime is in the list is based on the exponent.
So if you have a prime factorization 2^2 * 3^2 * 5^2 * 7^2 consider it as a list 22335577.
Now if you want to list the products of each different subset of this list you can do the following:
Start with an empty list L
For each member N in the list of primes
Multiply each member of L with N and add the new numbers you get to L if they are not already there
add N to L if it is not already there
end
And in the end L will include all the divisors of your original number (other than 1)
Now obviously you don't need to produce this list but instead if you have the primes and their exponents you can just loop for each separate prime from 1 to the exponent to achieve the same goal but I thought this was more illustrative.
I'm not sure this will work without some serious reworking [unless I'm dumb and misunderstood]
Let's say step one you have
2 2 3 3 5 5 7 7
If I start with 2 and multiply everything by it, the result is this [assuming I take it out from the list afterwards]
4 6 6 10 10 14 14
Now it starts to get tricky. 4 can not be multiplied by 2 again since it will yield 8, which is not one of the factors. However, everything else can be multiplied by 2 to get more factors
Basically, in a nutshell, there are certain parts of each list that can not be re-mulitplied. This would require each number to be an object and to store everything that was multiplied to get that number. Not sure if it's the best solution.
On August 31 2012 05:24 waxypants wrote:Show nested quote +On August 30 2012 15:51 frogmelter wrote:On August 29 2012 15:43 Blisse wrote:On August 29 2012 15:21 frogmelter wrote:On August 29 2012 14:53 Blisse wrote:On August 29 2012 14:49 frogmelter wrote:
For an assignment at school, I'm supposed to read in a number and find all the factors and bold the ones that are prime.
This is incredibly simple, except my professor put in
9223372036854775805
9223372036854775806
9223372036854775807
as some of the inputs that we need to test. This obviously takes a super long time to compute. I'm stumped on how I would optimize my code enough so that it would run quickly.
I can think of a clever way to get it to display all the factors, but not to calculate which ones are prime, especially for such a huge number. Can anyone give me some ideas? That's a very... interesting assignment, at least the way it's worded. By my gut, if you get the prime factorization, from there you can calculate all unique permutations of those that get you something less than the inputted number, which simply gives you all the factors of the number. Since you have the prime factorization, you should have all the primes you need. In my mind though, that seems like it'll take a very long time, but it might not! Seems like he just wants you to implement a very good prime factorization method. You'll have to make a call on whether you want to make one yourself or just follow the really optimized ones online. Calculating all the prime factors is no good, since I need to calculate all the factors as well. This is what I have so far. + Show Spoiler +
public void calcPrime()
{
if (value==2)
{
setPrime(true);
return;
}
if (value%3==0)
{
setPrime(false);
return;
}
if (value%10==5)
{
setPrime(false);
return;
}
if (value%2==0)
{
setPrime(false);
return;
}
if (value==1)
{
setPrime(false);
return;
}
for(long l=3; true; l++)
{
long square = l * l;
if (square > getValue())
{
break;
}
l = getNextTestPrime(l, square);
if (l == -1l)
{
setPrime(false);
return;
}
if(value%l==0)
{
setPrime(false);
return;
}
}
setPrime(true);
}
private Long getNextTestPrime(long l, long square)
{
while (l<square)
{
l=l+2;
if (!(l%3==0||l%5==0))
{
return l;
}
}
return (long) -1;
}
This will only test the numbers that are odd and are not divisible by 3 or end in 5 [the ones that end in 0 are caught by the mod 2 case] That's about as optimizes as I think I can get. Still no good on the 9 * 10^20 number so far. Hey, yup, I see what you're going for here, but I think you misunderstood my idea. I'm not in Computer Science, so I don't remember the proof or theorem by heart, but I took a course on proofs which included prime factorization. Which stated something like, given N = (f1)^(k1) * (f2)^(k2) * ... * (fn)^(kn), where f1, f2 ... fn are all primes, all possible factors can be determined by choosing different exponents, qm, such that 0 <= qm <= km, for 1 <= m <= n. I'll give an example since that's not super clear. + Show Spoiler +
Given 144 = 2^4 * 3^2 is the prime factorization. 2 and 3 are the ONLY prime factors, since that's what the prime factorization gives you.
From there, you have 2, with exponents from 0 to 4, and 3, with exponents from 0 to 2.
So all the factors are,
2^0 * 3^0 = 1
2^1 * 3^0 = 2
2^2 * 3^0 = 4
2^3 * 3^0 = 8
2^4 * 3^0 = 16
2^0 * 3^1 = 3
2^1 * 3^1 = 6
2^2 * 3^1 = 12
2^3 * 3^1 = 24
2^4 * 3^1 = 48
2^0 * 3^2 = 9
2^1 * 3^2 = 18
2^2 * 3^2 = 36
2^3 * 3^2 = 72
2^4 * 3^2 = 144
Hope that's a bit clearer. 1. Find the prime factorization. 2. Use the above method/theorem to calculate all the permutations, which gives you all the factors. By breaking the problem into parts, it should be a lot less complicated, no? I wish I remembered the name of the theorem to make it clearer for you. Best of luck. Well, I've written code to find all the prime factors. So I have a list of something like 2^2 * 3^2 * 5^2 * 7^2 However, I'm stumped on how I would multiply everything to get the actual factors. For example, the number 44100 is 2^2 * 3^2 * 5^2 * 7^2 I would have to multiply everything by each other ie. 2^1 * 3^1 2^1 * 3^2 2^1 * 3^1 * 5^1 2^1 * 3^1 * 5^2 2^1 * 3^1 * 7^1 2^1 * 3^1 * 7^2 2^1 * 3^1 * 5^1 * 7^1 2^1 * 3^1 * 5^1 * 7^2 2^2 * 3^1 2^2 * 3^2 2^2 * 3^1 * 5^1 2^2 * 3^1 * 5^2 2^2 * 3^1 * 7^1 2^2 * 3^1 * 7^2 2^2 * 3^1 * 5^1 * 7^1 2^2 * 3^1 * 5^1 * 7^2 I don't know how I would go about that, since there is a variable number of prime factors [If I chose 900, then it would only be 2^2 * 3^2 * 5^2]. If the number of prime factors were constant, it would be really simple I don't know how I would calculate it so that it multiplies every permutation. Especially since sometimes I would have to skip middle values ie. 2^2 * 3^0 * 5^2 * 7^0 * 11^2 This seems like some sort of recursion that I need to do perhaps... Any ideas are greatly appreciated Yes it is a recursion. Here is a python solution. I didn't completely test but the results look about right at a glance).
def factors_from_prime_factors(prime_factors):
if not prime_factors:
return []
else:
factors = factors_from_prime_factors(prime_factors[1:])
factors = prime_factors + map(lambda x: x*prime_factors[0], factors)
factors = list(set(factors))
factors.sort()
return factors
The prime factors must be given as a list like [2, 2, 3, 3, 5, 5, 7, 7] in the 44100 case. >>> factors_from_prime_factors([2, 2, 3, 3, 5, 5, 7, 7]) [2, 3, 4, 5, 6, 7, 10, 12, 14, 20, 28, 36, 60, 84, 180, 252, 900, 1260, 6300, 44100] edit: sorting can be taken out or done outside the function, same with the conversion to a set (it just removes duplicates), but I just put them in one function for simplicity and to look nice
Hmmm... Looks like you might be missing a few there.
http://www.wolframalpha.com/input/?i=factors of 44100
This tells me that there are 81 divisors for it, including 22050 [exactly half of it] which I don't see on your list
I have an idea for what I need to do. I just gotta code it.
On August 31 2012 05:34 zzdd wrote:Show nested quote +On August 30 2012 15:51 frogmelter wrote:On August 29 2012 15:43 Blisse wrote:On August 29 2012 15:21 frogmelter wrote:On August 29 2012 14:53 Blisse wrote:On August 29 2012 14:49 frogmelter wrote:
For an assignment at school, I'm supposed to read in a number and find all the factors and bold the ones that are prime.
This is incredibly simple, except my professor put in
9223372036854775805
9223372036854775806
9223372036854775807
as some of the inputs that we need to test. This obviously takes a super long time to compute. I'm stumped on how I would optimize my code enough so that it would run quickly.
I can think of a clever way to get it to display all the factors, but not to calculate which ones are prime, especially for such a huge number. Can anyone give me some ideas? That's a very... interesting assignment, at least the way it's worded. By my gut, if you get the prime factorization, from there you can calculate all unique permutations of those that get you something less than the inputted number, which simply gives you all the factors of the number. Since you have the prime factorization, you should have all the primes you need. In my mind though, that seems like it'll take a very long time, but it might not! Seems like he just wants you to implement a very good prime factorization method. You'll have to make a call on whether you want to make one yourself or just follow the really optimized ones online. Calculating all the prime factors is no good, since I need to calculate all the factors as well. This is what I have so far. + Show Spoiler +
public void calcPrime()
{
if (value==2)
{
setPrime(true);
return;
}
if (value%3==0)
{
setPrime(false);
return;
}
if (value%10==5)
{
setPrime(false);
return;
}
if (value%2==0)
{
setPrime(false);
return;
}
if (value==1)
{
setPrime(false);
return;
}
for(long l=3; true; l++)
{
long square = l * l;
if (square > getValue())
{
break;
}
l = getNextTestPrime(l, square);
if (l == -1l)
{
setPrime(false);
return;
}
if(value%l==0)
{
setPrime(false);
return;
}
}
setPrime(true);
}
private Long getNextTestPrime(long l, long square)
{
while (l<square)
{
l=l+2;
if (!(l%3==0||l%5==0))
{
return l;
}
}
return (long) -1;
}
This will only test the numbers that are odd and are not divisible by 3 or end in 5 [the ones that end in 0 are caught by the mod 2 case] That's about as optimizes as I think I can get. Still no good on the 9 * 10^20 number so far. Hey, yup, I see what you're going for here, but I think you misunderstood my idea. I'm not in Computer Science, so I don't remember the proof or theorem by heart, but I took a course on proofs which included prime factorization. Which stated something like, given N = (f1)^(k1) * (f2)^(k2) * ... * (fn)^(kn), where f1, f2 ... fn are all primes, all possible factors can be determined by choosing different exponents, qm, such that 0 <= qm <= km, for 1 <= m <= n. I'll give an example since that's not super clear. + Show Spoiler +
Given 144 = 2^4 * 3^2 is the prime factorization. 2 and 3 are the ONLY prime factors, since that's what the prime factorization gives you.
From there, you have 2, with exponents from 0 to 4, and 3, with exponents from 0 to 2.
So all the factors are,
2^0 * 3^0 = 1
2^1 * 3^0 = 2
2^2 * 3^0 = 4
2^3 * 3^0 = 8
2^4 * 3^0 = 16
2^0 * 3^1 = 3
2^1 * 3^1 = 6
2^2 * 3^1 = 12
2^3 * 3^1 = 24
2^4 * 3^1 = 48
2^0 * 3^2 = 9
2^1 * 3^2 = 18
2^2 * 3^2 = 36
2^3 * 3^2 = 72
2^4 * 3^2 = 144
Hope that's a bit clearer. 1. Find the prime factorization. 2. Use the above method/theorem to calculate all the permutations, which gives you all the factors. By breaking the problem into parts, it should be a lot less complicated, no? I wish I remembered the name of the theorem to make it clearer for you. Best of luck. Well, I've written code to find all the prime factors. So I have a list of something like 2^2 * 3^2 * 5^2 * 7^2 However, I'm stumped on how I would multiply everything to get the actual factors. For example, the number 44100 is 2^2 * 3^2 * 5^2 * 7^2 I would have to multiply everything by each other ie. 2^1 * 3^1 2^1 * 3^2 2^1 * 3^1 * 5^1 2^1 * 3^1 * 5^2 2^1 * 3^1 * 7^1 2^1 * 3^1 * 7^2 2^1 * 3^1 * 5^1 * 7^1 2^1 * 3^1 * 5^1 * 7^2 2^2 * 3^1 2^2 * 3^2 2^2 * 3^1 * 5^1 2^2 * 3^1 * 5^2 2^2 * 3^1 * 7^1 2^2 * 3^1 * 7^2 2^2 * 3^1 * 5^1 * 7^1 2^2 * 3^1 * 5^1 * 7^2 I don't know how I would go about that, since there is a variable number of prime factors [If I chose 900, then it would only be 2^2 * 3^2 * 5^2]. If the number of prime factors were constant, it would be really simple I don't know how I would calculate it so that it multiplies every permutation. Especially since sometimes I would have to skip middle values ie. 2^2 * 3^0 * 5^2 * 7^0 * 11^2 This seems like some sort of recursion that I need to do perhaps... Any ideas are greatly appreciated Google Miller Rabin. It will take you maybe an hour to do and is way simpler.
Well, looking at Miller Rabin, it seems to be a test to figure out whether a number is prime or not. My assignment is to find all the factors of a large number and list the ones that are prime. I'm not sure how Miller Rabin would help me there, since I already have all the prime factors.
|
Ahh this first post rly reminds me of myself..
I'm now at the 2nd semester and probably repeat my programming course.. before university I allready programmed languages such as php, actionscript, javascript, json and things like that. But since I learn java in the computer science course I feel really helpless and stupid. I hope it will change if I repeat the course and learn some java in my free time.
Sorry for my bad english
|
@frogmelter
I think I you misunderstood my post (or I was too unclear).
I said that you start with an empty list L.
So you have a list 22335577 which we shall call P.
Step 1. Add 2 to L because L is empty.
Step 2. Multiply 2*2 and add 4 to L, 2 is already there
Step 3. Multiply 2*3 and 4*3 and add 6 and 12 into L, add also 3 into L.
etc.
So as you move in P from left to right in each iteration you multiply all the products of all possible subsets of numbers left from the current position. This way you will get all the factors. (Not saying it is the best or even a good way)
edit:
For illustration here is the necessary code in R to produce the factors of your example. I just quickly tested it using R so I don't have to bother coding checks whether a number is already in the list.
P <- c(2,2,3,3,5,5,7,7)
L <- c(1)
for(i in 1:length(P))
{
tmp <- L*P[i]
L <- c(L,tmp)
L <- unique(L)
}
#Print length of L
length(L)
#Print L
sort(L)
Using this the output is the following:
+ Show Spoiler +
> length(L)
[1] 81
> sort(L)
[1] 1 2 3 4 5 6 7 9 10 12 14 15
[13] 18 20 21 25 28 30 35 36 42 45 49 50
[25] 60 63 70 75 84 90 98 100 105 126 140 147
[37] 150 175 180 196 210 225 245 252 294 300 315 350
[49] 420 441 450 490 525 588 630 700 735 882 900 980
[61] 1050 1225 1260 1470 1575 1764 2100 2205 2450 2940 3150 3675
[73] 4410 4900 6300 7350 8820 11025 14700 22050 44100
|
Hi, I'm trying to use NGen.exe on a simple .exe of mine.
(ngen install simplexe.exe)
But:
After the microsoft-Ads i get
"Uninstalling assembly C:\something\simplexe.exe because of an error during compilation: Failed to load the runtime. (Exception from HRESULT: 0x80....). Failed to load the runtime. (Exception from HRESULT: 0x80...)
All i can find in google is somethign about "assemblies" and "config files".
Can someone try to explain assemblies and config files to me OR can tell me, what's wrong with my .exe-File (or .NET installation, but i doubt that)?
|
Awesome programming related picture:
![[image loading]](http://4.bp.blogspot.com/-2EVlfIEiSd4/TpB42zwmuII/AAAAAAAAAIw/iYNA1tOaHWs/s400/header_hero_1.png)
|
On August 31 2012 12:56 frogmelter wrote:Show nested quote +On August 30 2012 17:48 spudde123 wrote:
I didn't spend too much time thinking whether the following is the best way of producing all the possible products but at least consider it food for thought!
Let's say you have a prime factorization, each prime with some exponent. Now consider that you drop the exponents and instead have a list of prime factors and the number of times a prime is in the list is based on the exponent.
So if you have a prime factorization 2^2 * 3^2 * 5^2 * 7^2 consider it as a list 22335577.
Now if you want to list the products of each different subset of this list you can do the following:
Start with an empty list L
For each member N in the list of primes
Multiply each member of L with N and add the new numbers you get to L if they are not already there
add N to L if it is not already there
end
And in the end L will include all the divisors of your original number (other than 1)
Now obviously you don't need to produce this list but instead if you have the primes and their exponents you can just loop for each separate prime from 1 to the exponent to achieve the same goal but I thought this was more illustrative.
I'm not sure this will work without some serious reworking [unless I'm dumb and misunderstood] Let's say step one you have 2 2 3 3 5 5 7 7 If I start with 2 and multiply everything by it, the result is this [assuming I take it out from the list afterwards] 4 6 6 10 10 14 14 Now it starts to get tricky. 4 can not be multiplied by 2 again since it will yield 8, which is not one of the factors. However, everything else can be multiplied by 2 to get more factors Basically, in a nutshell, there are certain parts of each list that can not be re-mulitplied. This would require each number to be an object and to store everything that was multiplied to get that number. Not sure if it's the best solution. Show nested quote +On August 31 2012 05:24 waxypants wrote:On August 30 2012 15:51 frogmelter wrote:On August 29 2012 15:43 Blisse wrote:On August 29 2012 15:21 frogmelter wrote:On August 29 2012 14:53 Blisse wrote:On August 29 2012 14:49 frogmelter wrote:
For an assignment at school, I'm supposed to read in a number and find all the factors and bold the ones that are prime.
This is incredibly simple, except my professor put in
9223372036854775805
9223372036854775806
9223372036854775807
as some of the inputs that we need to test. This obviously takes a super long time to compute. I'm stumped on how I would optimize my code enough so that it would run quickly.
I can think of a clever way to get it to display all the factors, but not to calculate which ones are prime, especially for such a huge number. Can anyone give me some ideas? That's a very... interesting assignment, at least the way it's worded. By my gut, if you get the prime factorization, from there you can calculate all unique permutations of those that get you something less than the inputted number, which simply gives you all the factors of the number. Since you have the prime factorization, you should have all the primes you need. In my mind though, that seems like it'll take a very long time, but it might not! Seems like he just wants you to implement a very good prime factorization method. You'll have to make a call on whether you want to make one yourself or just follow the really optimized ones online. Calculating all the prime factors is no good, since I need to calculate all the factors as well. This is what I have so far. + Show Spoiler +
public void calcPrime()
{
if (value==2)
{
setPrime(true);
return;
}
if (value%3==0)
{
setPrime(false);
return;
}
if (value%10==5)
{
setPrime(false);
return;
}
if (value%2==0)
{
setPrime(false);
return;
}
if (value==1)
{
setPrime(false);
return;
}
for(long l=3; true; l++)
{
long square = l * l;
if (square > getValue())
{
break;
}
l = getNextTestPrime(l, square);
if (l == -1l)
{
setPrime(false);
return;
}
if(value%l==0)
{
setPrime(false);
return;
}
}
setPrime(true);
}
private Long getNextTestPrime(long l, long square)
{
while (l<square)
{
l=l+2;
if (!(l%3==0||l%5==0))
{
return l;
}
}
return (long) -1;
}
This will only test the numbers that are odd and are not divisible by 3 or end in 5 [the ones that end in 0 are caught by the mod 2 case] That's about as optimizes as I think I can get. Still no good on the 9 * 10^20 number so far. Hey, yup, I see what you're going for here, but I think you misunderstood my idea. I'm not in Computer Science, so I don't remember the proof or theorem by heart, but I took a course on proofs which included prime factorization. Which stated something like, given N = (f1)^(k1) * (f2)^(k2) * ... * (fn)^(kn), where f1, f2 ... fn are all primes, all possible factors can be determined by choosing different exponents, qm, such that 0 <= qm <= km, for 1 <= m <= n. I'll give an example since that's not super clear. + Show Spoiler +
Given 144 = 2^4 * 3^2 is the prime factorization. 2 and 3 are the ONLY prime factors, since that's what the prime factorization gives you.
From there, you have 2, with exponents from 0 to 4, and 3, with exponents from 0 to 2.
So all the factors are,
2^0 * 3^0 = 1
2^1 * 3^0 = 2
2^2 * 3^0 = 4
2^3 * 3^0 = 8
2^4 * 3^0 = 16
2^0 * 3^1 = 3
2^1 * 3^1 = 6
2^2 * 3^1 = 12
2^3 * 3^1 = 24
2^4 * 3^1 = 48
2^0 * 3^2 = 9
2^1 * 3^2 = 18
2^2 * 3^2 = 36
2^3 * 3^2 = 72
2^4 * 3^2 = 144
Hope that's a bit clearer. 1. Find the prime factorization. 2. Use the above method/theorem to calculate all the permutations, which gives you all the factors. By breaking the problem into parts, it should be a lot less complicated, no? I wish I remembered the name of the theorem to make it clearer for you. Best of luck. Well, I've written code to find all the prime factors. So I have a list of something like 2^2 * 3^2 * 5^2 * 7^2 However, I'm stumped on how I would multiply everything to get the actual factors. For example, the number 44100 is 2^2 * 3^2 * 5^2 * 7^2 I would have to multiply everything by each other ie. 2^1 * 3^1 2^1 * 3^2 2^1 * 3^1 * 5^1 2^1 * 3^1 * 5^2 2^1 * 3^1 * 7^1 2^1 * 3^1 * 7^2 2^1 * 3^1 * 5^1 * 7^1 2^1 * 3^1 * 5^1 * 7^2 2^2 * 3^1 2^2 * 3^2 2^2 * 3^1 * 5^1 2^2 * 3^1 * 5^2 2^2 * 3^1 * 7^1 2^2 * 3^1 * 7^2 2^2 * 3^1 * 5^1 * 7^1 2^2 * 3^1 * 5^1 * 7^2 I don't know how I would go about that, since there is a variable number of prime factors [If I chose 900, then it would only be 2^2 * 3^2 * 5^2]. If the number of prime factors were constant, it would be really simple I don't know how I would calculate it so that it multiplies every permutation. Especially since sometimes I would have to skip middle values ie. 2^2 * 3^0 * 5^2 * 7^0 * 11^2 This seems like some sort of recursion that I need to do perhaps... Any ideas are greatly appreciated Yes it is a recursion. Here is a python solution. I didn't completely test but the results look about right at a glance).
def factors_from_prime_factors(prime_factors):
if not prime_factors:
return []
else:
factors = factors_from_prime_factors(prime_factors[1:])
factors = prime_factors + map(lambda x: x*prime_factors[0], factors)
factors = list(set(factors))
factors.sort()
return factors
The prime factors must be given as a list like [2, 2, 3, 3, 5, 5, 7, 7] in the 44100 case. >>> factors_from_prime_factors([2, 2, 3, 3, 5, 5, 7, 7]) [2, 3, 4, 5, 6, 7, 10, 12, 14, 20, 28, 36, 60, 84, 180, 252, 900, 1260, 6300, 44100] edit: sorting can be taken out or done outside the function, same with the conversion to a set (it just removes duplicates), but I just put them in one function for simplicity and to look nice Hmmm... Looks like you might be missing a few there. http://www.wolframalpha.com/input/?i=factors of 44100This tells me that there are 81 divisors for it, including 22050 [exactly half of it] which I don't see on your list I have an idea for what I need to do. I just gotta code it. Show nested quote +On August 31 2012 05:34 zzdd wrote:On August 30 2012 15:51 frogmelter wrote:On August 29 2012 15:43 Blisse wrote:On August 29 2012 15:21 frogmelter wrote:On August 29 2012 14:53 Blisse wrote:On August 29 2012 14:49 frogmelter wrote:
For an assignment at school, I'm supposed to read in a number and find all the factors and bold the ones that are prime.
This is incredibly simple, except my professor put in
9223372036854775805
9223372036854775806
9223372036854775807
as some of the inputs that we need to test. This obviously takes a super long time to compute. I'm stumped on how I would optimize my code enough so that it would run quickly.
I can think of a clever way to get it to display all the factors, but not to calculate which ones are prime, especially for such a huge number. Can anyone give me some ideas? That's a very... interesting assignment, at least the way it's worded. By my gut, if you get the prime factorization, from there you can calculate all unique permutations of those that get you something less than the inputted number, which simply gives you all the factors of the number. Since you have the prime factorization, you should have all the primes you need. In my mind though, that seems like it'll take a very long time, but it might not! Seems like he just wants you to implement a very good prime factorization method. You'll have to make a call on whether you want to make one yourself or just follow the really optimized ones online. Calculating all the prime factors is no good, since I need to calculate all the factors as well. This is what I have so far. + Show Spoiler +
public void calcPrime()
{
if (value==2)
{
setPrime(true);
return;
}
if (value%3==0)
{
setPrime(false);
return;
}
if (value%10==5)
{
setPrime(false);
return;
}
if (value%2==0)
{
setPrime(false);
return;
}
if (value==1)
{
setPrime(false);
return;
}
for(long l=3; true; l++)
{
long square = l * l;
if (square > getValue())
{
break;
}
l = getNextTestPrime(l, square);
if (l == -1l)
{
setPrime(false);
return;
}
if(value%l==0)
{
setPrime(false);
return;
}
}
setPrime(true);
}
private Long getNextTestPrime(long l, long square)
{
while (l<square)
{
l=l+2;
if (!(l%3==0||l%5==0))
{
return l;
}
}
return (long) -1;
}
This will only test the numbers that are odd and are not divisible by 3 or end in 5 [the ones that end in 0 are caught by the mod 2 case] That's about as optimizes as I think I can get. Still no good on the 9 * 10^20 number so far. Hey, yup, I see what you're going for here, but I think you misunderstood my idea. I'm not in Computer Science, so I don't remember the proof or theorem by heart, but I took a course on proofs which included prime factorization. Which stated something like, given N = (f1)^(k1) * (f2)^(k2) * ... * (fn)^(kn), where f1, f2 ... fn are all primes, all possible factors can be determined by choosing different exponents, qm, such that 0 <= qm <= km, for 1 <= m <= n. I'll give an example since that's not super clear. + Show Spoiler +
Given 144 = 2^4 * 3^2 is the prime factorization. 2 and 3 are the ONLY prime factors, since that's what the prime factorization gives you.
From there, you have 2, with exponents from 0 to 4, and 3, with exponents from 0 to 2.
So all the factors are,
2^0 * 3^0 = 1
2^1 * 3^0 = 2
2^2 * 3^0 = 4
2^3 * 3^0 = 8
2^4 * 3^0 = 16
2^0 * 3^1 = 3
2^1 * 3^1 = 6
2^2 * 3^1 = 12
2^3 * 3^1 = 24
2^4 * 3^1 = 48
2^0 * 3^2 = 9
2^1 * 3^2 = 18
2^2 * 3^2 = 36
2^3 * 3^2 = 72
2^4 * 3^2 = 144
Hope that's a bit clearer. 1. Find the prime factorization. 2. Use the above method/theorem to calculate all the permutations, which gives you all the factors. By breaking the problem into parts, it should be a lot less complicated, no? I wish I remembered the name of the theorem to make it clearer for you. Best of luck. Well, I've written code to find all the prime factors. So I have a list of something like 2^2 * 3^2 * 5^2 * 7^2 However, I'm stumped on how I would multiply everything to get the actual factors. For example, the number 44100 is 2^2 * 3^2 * 5^2 * 7^2 I would have to multiply everything by each other ie. 2^1 * 3^1 2^1 * 3^2 2^1 * 3^1 * 5^1 2^1 * 3^1 * 5^2 2^1 * 3^1 * 7^1 2^1 * 3^1 * 7^2 2^1 * 3^1 * 5^1 * 7^1 2^1 * 3^1 * 5^1 * 7^2 2^2 * 3^1 2^2 * 3^2 2^2 * 3^1 * 5^1 2^2 * 3^1 * 5^2 2^2 * 3^1 * 7^1 2^2 * 3^1 * 7^2 2^2 * 3^1 * 5^1 * 7^1 2^2 * 3^1 * 5^1 * 7^2 I don't know how I would go about that, since there is a variable number of prime factors [If I chose 900, then it would only be 2^2 * 3^2 * 5^2]. If the number of prime factors were constant, it would be really simple I don't know how I would calculate it so that it multiplies every permutation. Especially since sometimes I would have to skip middle values ie. 2^2 * 3^0 * 5^2 * 7^0 * 11^2 This seems like some sort of recursion that I need to do perhaps... Any ideas are greatly appreciated Google Miller Rabin. It will take you maybe an hour to do and is way simpler. Well, looking at Miller Rabin, it seems to be a test to figure out whether a number is prime or not. My assignment is to find all the factors of a large number and list the ones that are prime. I'm not sure how Miller Rabin would help me there, since I already have all the prime factors.
You're right, oops. Guess checking for 22050 should have been obvious before I posted it  Hmm now I'm going to have to go back and figure out where I went wrong.
|
On September 01 2012 03:23 waxypants wrote:Show nested quote +On August 31 2012 12:56 frogmelter wrote:On August 30 2012 17:48 spudde123 wrote:
I didn't spend too much time thinking whether the following is the best way of producing all the possible products but at least consider it food for thought!
Let's say you have a prime factorization, each prime with some exponent. Now consider that you drop the exponents and instead have a list of prime factors and the number of times a prime is in the list is based on the exponent.
So if you have a prime factorization 2^2 * 3^2 * 5^2 * 7^2 consider it as a list 22335577.
Now if you want to list the products of each different subset of this list you can do the following:
Start with an empty list L
For each member N in the list of primes
Multiply each member of L with N and add the new numbers you get to L if they are not already there
add N to L if it is not already there
end
And in the end L will include all the divisors of your original number (other than 1)
Now obviously you don't need to produce this list but instead if you have the primes and their exponents you can just loop for each separate prime from 1 to the exponent to achieve the same goal but I thought this was more illustrative.
I'm not sure this will work without some serious reworking [unless I'm dumb and misunderstood] Let's say step one you have 2 2 3 3 5 5 7 7 If I start with 2 and multiply everything by it, the result is this [assuming I take it out from the list afterwards] 4 6 6 10 10 14 14 Now it starts to get tricky. 4 can not be multiplied by 2 again since it will yield 8, which is not one of the factors. However, everything else can be multiplied by 2 to get more factors Basically, in a nutshell, there are certain parts of each list that can not be re-mulitplied. This would require each number to be an object and to store everything that was multiplied to get that number. Not sure if it's the best solution. On August 31 2012 05:24 waxypants wrote:On August 30 2012 15:51 frogmelter wrote:On August 29 2012 15:43 Blisse wrote:On August 29 2012 15:21 frogmelter wrote:On August 29 2012 14:53 Blisse wrote:On August 29 2012 14:49 frogmelter wrote:
For an assignment at school, I'm supposed to read in a number and find all the factors and bold the ones that are prime.
This is incredibly simple, except my professor put in
9223372036854775805
9223372036854775806
9223372036854775807
as some of the inputs that we need to test. This obviously takes a super long time to compute. I'm stumped on how I would optimize my code enough so that it would run quickly.
I can think of a clever way to get it to display all the factors, but not to calculate which ones are prime, especially for such a huge number. Can anyone give me some ideas? That's a very... interesting assignment, at least the way it's worded. By my gut, if you get the prime factorization, from there you can calculate all unique permutations of those that get you something less than the inputted number, which simply gives you all the factors of the number. Since you have the prime factorization, you should have all the primes you need. In my mind though, that seems like it'll take a very long time, but it might not! Seems like he just wants you to implement a very good prime factorization method. You'll have to make a call on whether you want to make one yourself or just follow the really optimized ones online. Calculating all the prime factors is no good, since I need to calculate all the factors as well. This is what I have so far. + Show Spoiler +
public void calcPrime()
{
if (value==2)
{
setPrime(true);
return;
}
if (value%3==0)
{
setPrime(false);
return;
}
if (value%10==5)
{
setPrime(false);
return;
}
if (value%2==0)
{
setPrime(false);
return;
}
if (value==1)
{
setPrime(false);
return;
}
for(long l=3; true; l++)
{
long square = l * l;
if (square > getValue())
{
break;
}
l = getNextTestPrime(l, square);
if (l == -1l)
{
setPrime(false);
return;
}
if(value%l==0)
{
setPrime(false);
return;
}
}
setPrime(true);
}
private Long getNextTestPrime(long l, long square)
{
while (l<square)
{
l=l+2;
if (!(l%3==0||l%5==0))
{
return l;
}
}
return (long) -1;
}
This will only test the numbers that are odd and are not divisible by 3 or end in 5 [the ones that end in 0 are caught by the mod 2 case] That's about as optimizes as I think I can get. Still no good on the 9 * 10^20 number so far. Hey, yup, I see what you're going for here, but I think you misunderstood my idea. I'm not in Computer Science, so I don't remember the proof or theorem by heart, but I took a course on proofs which included prime factorization. Which stated something like, given N = (f1)^(k1) * (f2)^(k2) * ... * (fn)^(kn), where f1, f2 ... fn are all primes, all possible factors can be determined by choosing different exponents, qm, such that 0 <= qm <= km, for 1 <= m <= n. I'll give an example since that's not super clear. + Show Spoiler +
Given 144 = 2^4 * 3^2 is the prime factorization. 2 and 3 are the ONLY prime factors, since that's what the prime factorization gives you.
From there, you have 2, with exponents from 0 to 4, and 3, with exponents from 0 to 2.
So all the factors are,
2^0 * 3^0 = 1
2^1 * 3^0 = 2
2^2 * 3^0 = 4
2^3 * 3^0 = 8
2^4 * 3^0 = 16
2^0 * 3^1 = 3
2^1 * 3^1 = 6
2^2 * 3^1 = 12
2^3 * 3^1 = 24
2^4 * 3^1 = 48
2^0 * 3^2 = 9
2^1 * 3^2 = 18
2^2 * 3^2 = 36
2^3 * 3^2 = 72
2^4 * 3^2 = 144
Hope that's a bit clearer. 1. Find the prime factorization. 2. Use the above method/theorem to calculate all the permutations, which gives you all the factors. By breaking the problem into parts, it should be a lot less complicated, no? I wish I remembered the name of the theorem to make it clearer for you. Best of luck. Well, I've written code to find all the prime factors. So I have a list of something like 2^2 * 3^2 * 5^2 * 7^2 However, I'm stumped on how I would multiply everything to get the actual factors. For example, the number 44100 is 2^2 * 3^2 * 5^2 * 7^2 I would have to multiply everything by each other ie. 2^1 * 3^1 2^1 * 3^2 2^1 * 3^1 * 5^1 2^1 * 3^1 * 5^2 2^1 * 3^1 * 7^1 2^1 * 3^1 * 7^2 2^1 * 3^1 * 5^1 * 7^1 2^1 * 3^1 * 5^1 * 7^2 2^2 * 3^1 2^2 * 3^2 2^2 * 3^1 * 5^1 2^2 * 3^1 * 5^2 2^2 * 3^1 * 7^1 2^2 * 3^1 * 7^2 2^2 * 3^1 * 5^1 * 7^1 2^2 * 3^1 * 5^1 * 7^2 I don't know how I would go about that, since there is a variable number of prime factors [If I chose 900, then it would only be 2^2 * 3^2 * 5^2]. If the number of prime factors were constant, it would be really simple I don't know how I would calculate it so that it multiplies every permutation. Especially since sometimes I would have to skip middle values ie. 2^2 * 3^0 * 5^2 * 7^0 * 11^2 This seems like some sort of recursion that I need to do perhaps... Any ideas are greatly appreciated Yes it is a recursion. Here is a python solution. I didn't completely test but the results look about right at a glance).
def factors_from_prime_factors(prime_factors):
if not prime_factors:
return []
else:
factors = factors_from_prime_factors(prime_factors[1:])
factors = prime_factors + map(lambda x: x*prime_factors[0], factors)
factors = list(set(factors))
factors.sort()
return factors
The prime factors must be given as a list like [2, 2, 3, 3, 5, 5, 7, 7] in the 44100 case. >>> factors_from_prime_factors([2, 2, 3, 3, 5, 5, 7, 7]) [2, 3, 4, 5, 6, 7, 10, 12, 14, 20, 28, 36, 60, 84, 180, 252, 900, 1260, 6300, 44100] edit: sorting can be taken out or done outside the function, same with the conversion to a set (it just removes duplicates), but I just put them in one function for simplicity and to look nice Hmmm... Looks like you might be missing a few there. http://www.wolframalpha.com/input/?i=factors of 44100This tells me that there are 81 divisors for it, including 22050 [exactly half of it] which I don't see on your list I have an idea for what I need to do. I just gotta code it. On August 31 2012 05:34 zzdd wrote:On August 30 2012 15:51 frogmelter wrote:On August 29 2012 15:43 Blisse wrote:On August 29 2012 15:21 frogmelter wrote:On August 29 2012 14:53 Blisse wrote:On August 29 2012 14:49 frogmelter wrote:
For an assignment at school, I'm supposed to read in a number and find all the factors and bold the ones that are prime.
This is incredibly simple, except my professor put in
9223372036854775805
9223372036854775806
9223372036854775807
as some of the inputs that we need to test. This obviously takes a super long time to compute. I'm stumped on how I would optimize my code enough so that it would run quickly.
I can think of a clever way to get it to display all the factors, but not to calculate which ones are prime, especially for such a huge number. Can anyone give me some ideas? That's a very... interesting assignment, at least the way it's worded. By my gut, if you get the prime factorization, from there you can calculate all unique permutations of those that get you something less than the inputted number, which simply gives you all the factors of the number. Since you have the prime factorization, you should have all the primes you need. In my mind though, that seems like it'll take a very long time, but it might not! Seems like he just wants you to implement a very good prime factorization method. You'll have to make a call on whether you want to make one yourself or just follow the really optimized ones online. Calculating all the prime factors is no good, since I need to calculate all the factors as well. This is what I have so far. + Show Spoiler +
public void calcPrime()
{
if (value==2)
{
setPrime(true);
return;
}
if (value%3==0)
{
setPrime(false);
return;
}
if (value%10==5)
{
setPrime(false);
return;
}
if (value%2==0)
{
setPrime(false);
return;
}
if (value==1)
{
setPrime(false);
return;
}
for(long l=3; true; l++)
{
long square = l * l;
if (square > getValue())
{
break;
}
l = getNextTestPrime(l, square);
if (l == -1l)
{
setPrime(false);
return;
}
if(value%l==0)
{
setPrime(false);
return;
}
}
setPrime(true);
}
private Long getNextTestPrime(long l, long square)
{
while (l<square)
{
l=l+2;
if (!(l%3==0||l%5==0))
{
return l;
}
}
return (long) -1;
}
This will only test the numbers that are odd and are not divisible by 3 or end in 5 [the ones that end in 0 are caught by the mod 2 case] That's about as optimizes as I think I can get. Still no good on the 9 * 10^20 number so far. Hey, yup, I see what you're going for here, but I think you misunderstood my idea. I'm not in Computer Science, so I don't remember the proof or theorem by heart, but I took a course on proofs which included prime factorization. Which stated something like, given N = (f1)^(k1) * (f2)^(k2) * ... * (fn)^(kn), where f1, f2 ... fn are all primes, all possible factors can be determined by choosing different exponents, qm, such that 0 <= qm <= km, for 1 <= m <= n. I'll give an example since that's not super clear. + Show Spoiler +
Given 144 = 2^4 * 3^2 is the prime factorization. 2 and 3 are the ONLY prime factors, since that's what the prime factorization gives you.
From there, you have 2, with exponents from 0 to 4, and 3, with exponents from 0 to 2.
So all the factors are,
2^0 * 3^0 = 1
2^1 * 3^0 = 2
2^2 * 3^0 = 4
2^3 * 3^0 = 8
2^4 * 3^0 = 16
2^0 * 3^1 = 3
2^1 * 3^1 = 6
2^2 * 3^1 = 12
2^3 * 3^1 = 24
2^4 * 3^1 = 48
2^0 * 3^2 = 9
2^1 * 3^2 = 18
2^2 * 3^2 = 36
2^3 * 3^2 = 72
2^4 * 3^2 = 144
Hope that's a bit clearer. 1. Find the prime factorization. 2. Use the above method/theorem to calculate all the permutations, which gives you all the factors. By breaking the problem into parts, it should be a lot less complicated, no? I wish I remembered the name of the theorem to make it clearer for you. Best of luck. Well, I've written code to find all the prime factors. So I have a list of something like 2^2 * 3^2 * 5^2 * 7^2 However, I'm stumped on how I would multiply everything to get the actual factors. For example, the number 44100 is 2^2 * 3^2 * 5^2 * 7^2 I would have to multiply everything by each other ie. 2^1 * 3^1 2^1 * 3^2 2^1 * 3^1 * 5^1 2^1 * 3^1 * 5^2 2^1 * 3^1 * 7^1 2^1 * 3^1 * 7^2 2^1 * 3^1 * 5^1 * 7^1 2^1 * 3^1 * 5^1 * 7^2 2^2 * 3^1 2^2 * 3^2 2^2 * 3^1 * 5^1 2^2 * 3^1 * 5^2 2^2 * 3^1 * 7^1 2^2 * 3^1 * 7^2 2^2 * 3^1 * 5^1 * 7^1 2^2 * 3^1 * 5^1 * 7^2 I don't know how I would go about that, since there is a variable number of prime factors [If I chose 900, then it would only be 2^2 * 3^2 * 5^2]. If the number of prime factors were constant, it would be really simple I don't know how I would calculate it so that it multiplies every permutation. Especially since sometimes I would have to skip middle values ie. 2^2 * 3^0 * 5^2 * 7^0 * 11^2 This seems like some sort of recursion that I need to do perhaps... Any ideas are greatly appreciated Google Miller Rabin. It will take you maybe an hour to do and is way simpler. Well, looking at Miller Rabin, it seems to be a test to figure out whether a number is prime or not. My assignment is to find all the factors of a large number and list the ones that are prime. I'm not sure how Miller Rabin would help me there, since I already have all the prime factors. You're right, oops. Guess checking for 22050 should have been obvious before I posted it Hmm now I'm going to have to go back and figure out where I went wrong.
Ahh was missing one little part. Seems ok now. I know you probably don't need this, but just posting for my own satisfaction
def factors_from_prime_factors(prime_factors):
if not prime_factors:
return []
else:
factors = factors_from_prime_factors(prime_factors[1:])
factors = prime_factors + factors + map(lambda x: x*prime_factors[0], factors)
factors = list(set(factors))
factors.sort()
return factors
>>> factors = factors_from_prime_factors([2, 2, 3, 3, 5, 5, 7, 7])
>>> print factors
[2, 3, 4, 5, 6, 7, 9, 10, 12, 14, 15, 18, 20, 21, 25, 28, 30, 35, 36, 42, 45, 49, 50, 60, 63, 70, 75
, 84, 90, 98, 100, 105, 126, 140, 147, 150, 175, 180, 196, 210, 225, 245, 252, 294, 300, 315, 350, 4
20, 441, 450, 490, 525, 588, 630, 700, 735, 882, 900, 980, 1050, 1225, 1260, 1470, 1575, 1764, 2100,
2205, 2450, 2940, 3150, 3675, 4410, 4900, 6300, 7350, 8820, 11025, 14700, 22050, 44100]
>>> len(factors)
80
|
Hi guys, I have a question regarding multithreading in c++.
Currently I have a number of threads (say 5), and a number of jobs (say 100). Right now, Thread 1 solves jobs 0, 5, 10, ...,
Thread 2 solves jobs 1, 6, 11, ... etc.
However this sucks if the jobs take a different amount of time. What i would like to do is have some sort of simple function/method that the threads can call and get a jobnumber, similar to this:
int getJobNumber()
{
static unsigned int jobNumber = 0;
return jobNumber++;
}
- only that it has to be safe for multithreaded use. Any pointers to what i should look into? Thanks
|
On September 01 2012 03:50 LukeNukeEm wrote:Hi guys, I have a question regarding multithreading in c++. Currently I have a number of threads (say 5), and a number of jobs (say 100). Right now, Thread 1 solves jobs 0, 5, 10, ..., Thread 2 solves jobs 1, 6, 11, ... etc. However this sucks if the jobs take a different amount of time. What i would like to do is have some sort of simple function/method that the threads can call and get a jobnumber, similar to this: int getJobNumber()
{
static unsigned int jobNumber = 0;
return jobNumber++;
} - only that it has to be safe for multithreaded use. Any pointers to what i should look into? Thanks
Use a mutex.
|
|
|
|
|
|
EPT
