• Log InLog In
  • Register
Liquid`
Team Liquid Liquipedia
EDT 21:22
CEST 03:22
KST 10:22
  • Home
  • Forum
  • Calendar
  • Streams
  • Liquipedia
  • Features
  • Store
  • EPT
  • TL+
  • StarCraft 2
  • Brood War
  • Smash
  • Heroes
  • Counter-Strike
  • Overwatch
  • Liquibet
  • Fantasy StarCraft
  • TLPD
  • StarCraft 2
  • Brood War
  • Blogs
Forum Sidebar
Events/Features
News
Featured News
[ASL19] Finals Recap: Standing Tall9HomeStory Cup 27 - Info & Preview18Classic wins Code S Season 2 (2025)16Code S RO4 & Finals Preview: herO, Rogue, Classic, GuMiho0TL Team Map Contest #5: Presented by Monster Energy6
Community News
Flash Announces Hiatus From ASL54Weekly Cups (June 23-29): Reynor in world title form?12FEL Cracov 2025 (July 27) - $8000 live event16Esports World Cup 2025 - Final Player Roster16Weekly Cups (June 16-22): Clem strikes back1
StarCraft 2
General
The SCII GOAT: A statistical Evaluation The GOAT ranking of GOAT rankings Statistics for vetoed/disliked maps How does the number of casters affect your enjoyment of esports? Esports World Cup 2025 - Final Player Roster
Tourneys
Korean Starcraft League Week 77 Master Swan Open (Global Bronze-Master 2) RSL: Revival, a new crowdfunded tournament series [GSL 2025] Code S: Season 2 - Semi Finals & Finals $5,100+ SEL Season 2 Championship (SC: Evo)
Strategy
How did i lose this ZvP, whats the proper response Simple Questions Simple Answers
Custom Maps
[UMS] Zillion Zerglings
External Content
Mutation # 480 Moths to the Flame Mutation # 479 Worn Out Welcome Mutation # 478 Instant Karma Mutation # 477 Slow and Steady
Brood War
General
Flash Announces Hiatus From ASL BGH Auto Balance -> http://bghmmr.eu/ Player “Jedi” cheat on CSL Unit and Spell Similarities Help: rep cant save
Tourneys
[Megathread] Daily Proleagues [BSL20] Grand Finals - Sunday 20:00 CET Small VOD Thread 2.0 [BSL20] GosuLeague RO16 - Tue & Wed 20:00+CET
Strategy
Simple Questions, Simple Answers I am doing this better than progamers do.
Other Games
General Games
Stormgate/Frost Giant Megathread Nintendo Switch Thread Path of Exile What do you want from future RTS games? Beyond All Reason
Dota 2
Official 'what is Dota anymore' discussion
League of Legends
Heroes of the Storm
Simple Questions, Simple Answers Heroes of the Storm 2.0
Hearthstone
Heroes of StarCraft mini-set
TL Mafia
TL Mafia Community Thread Vanilla Mini Mafia
Community
General
Things Aren’t Peaceful in Palestine US Politics Mega-thread Trading/Investing Thread Russo-Ukrainian War Thread The Games Industry And ATVI
Fan Clubs
SKT1 Classic Fan Club! Maru Fan Club
Media & Entertainment
Anime Discussion Thread [Manga] One Piece [\m/] Heavy Metal Thread
Sports
Formula 1 Discussion 2024 - 2025 Football Thread NBA General Discussion TeamLiquid Health and Fitness Initiative For 2023 NHL Playoffs 2024
World Cup 2022
Tech Support
Computer Build, Upgrade & Buying Resource Thread
TL Community
Blogs
Culture Clash in Video Games…
TrAiDoS
from making sc maps to makin…
Husyelt
Blog #2
tankgirl
StarCraft improvement
iopq
Trip to the Zoo
micronesia
Customize Sidebar...

Website Feedback

Closed Threads



Active: 616 users

The Big Programming Thread - Page 160

Forum Index > General Forum
Post a Reply
Prev 1 158 159 160 161 162 1031 Next
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.
meatpudding
Profile Joined March 2011
Australia520 Posts
August 28 2012 05:23 GMT
#3181
Blisse

You could create a dict to count the elements like this:


m = {} # count of items in a
n = {} # count of items in b

for i in a:
if(m.has_key(i)):
m[i] += 1
else:
m[i] = 1


for i in b:
if(n.has_key(i)):
n[i] += 1
else:
n[i] = 1


Then you can do some quick lookups to determine which values to keep. Eg:


# Your logic here...
uniqueItems = []
for i in m:
if m[i] > 1 and i in n:
uniqueItems.append(i)


HTH
Be excellent to each other.
Blisse
Profile Blog Joined July 2010
Canada3710 Posts
August 28 2012 05:46 GMT
#3182
On August 28 2012 14:23 meatpudding wrote:
+ Show Spoiler +
Blisse

You could create a dict to count the elements like this:


m = {} # count of items in a
n = {} # count of items in b

for i in a:
if(m.has_key(i)):
m[i] += 1
else:
m[i] = 1


for i in b:
if(n.has_key(i)):
n[i] += 1
else:
n[i] = 1


Then you can do some quick lookups to determine which values to keep. Eg:


# Your logic here...
uniqueItems = []
for i in m:
if m[i] > 1 and i in n:
uniqueItems.append(i)


HTH



ooo, looking it over now, it looks very promising. I must review it tomorrow. Thanks for your help!
There is no one like you in the universe.
phar
Profile Joined August 2011
United States1080 Posts
Last Edited: 2012-08-28 05:53:06
August 28 2012 05:51 GMT
#3183
^ meatpudding's solution is probably cool one, however something thing to note:

On August 28 2012 10:28 Blisse wrote:The two lists can possibly have over 20,000 items each.


Are you guaranteed to have the lists be small enough to be in memory? The dictionary approach becomes rapidly less appealing if you have to go out to disk.

(20k strings is pretty small though, assuming each string is <1k or so)

Assuming this is for an undergrad class and you're not in China or CMU or something, it may be safe to assume it's small enough to hold in memory.
Who after all is today speaking about the destruction of the Armenians?
MisterD
Profile Blog Joined June 2010
Germany1338 Posts
August 28 2012 08:35 GMT
#3184
if your language doesn't have established data structures don't use it or write your own :p the dict approach mentioned above basically implements a bag, and you can just as easily get a set by simply associating each key with a fixed value. If you have a bag and set, the implementation becomes pretty straight forward (dirty java snippet using apache commons collections classes):


// inputs..
List a = ...
List b = ...
// count the number of occurances in each array
Bag bagA = new HashBag();
bagA.addAll(a);
Bag bagB = new HashBag();
bagB.addAll(b);
// calculate a set of all different strings for iteration
Set allStrings = new HashSet();
allStrings.addAll(bagA.uniqueSet());
allStrings.addAll(bagB.uniqueSet());
// iterate through all strings
Bag result = new HashBag();
for(String string : allStrings) {
// for each string, store as many copies as the absolute difference in occurance count in a and b
result.add(string, Math.abs(bagA.getCount(string) - bagB.getCount(string));
}
// and done
System.out.println(result);


that runs in linear time and doesn't touch the initial lists/arrays at all except for reading them. I assume you *could* implement this with about 50% less requirements in both time and memory if you really want to, but that just makes the algorithm harder to read, and half of linear is still linear, so it doesn't really matter all that much unless you happen to have real time constraints.
Gold isn't everything in life... you need wood, too!
Leafty
Profile Joined July 2012
France84 Posts
August 28 2012 10:04 GMT
#3185
On August 28 2012 10:28 Blisse wrote:
A common example of the list would be, given

a = [1,1,3,2,3,3,2,2]
b = [1,1,2,3,2]

I need the following by the end

a = [2,3,3]
b = []



Why do you expect

a = [2,3,3]
b = []


instead of

a = [3,3,2]
b = []


if you say you expect the order to be preserved?
KaiserJohan
Profile Joined May 2010
Sweden1808 Posts
August 28 2012 10:56 GMT
#3186
Even if you aren't a game developer, you should read this blog:

http://bitsquid.blogspot.se/2012/08/cleaning-bad-code.html

so awesome written, the part about cleaning bad code is hilarious. Here's an excerpt:

Megafunctions. You have heard about them. These mythic creatures that dwell in the deepest recesses of the darkest codebases. Broken programmers talk about them in dusky bars, their sanity shattered by their encounters: "I just kept scrolling and scrolling. I couldn't believe my eyes. It was 12 000 lines long."
England will fight to the last American
Deleted User 101379
Profile Blog Joined August 2010
4849 Posts
Last Edited: 2012-08-28 11:22:15
August 28 2012 11:15 GMT
#3187
On August 28 2012 19:56 KaiserJohan wrote:
Even if you aren't a game developer, you should read this blog:

http://bitsquid.blogspot.se/2012/08/cleaning-bad-code.html

so awesome written, the part about cleaning bad code is hilarious. Here's an excerpt:

Show nested quote +
Megafunctions. You have heard about them. These mythic creatures that dwell in the deepest recesses of the darkest codebases. Broken programmers talk about them in dusky bars, their sanity shattered by their encounters: "I just kept scrolling and scrolling. I couldn't believe my eyes. It was 12 000 lines long."


It's only hilarious if you don't face them every single day at work.

Megafunctions? I would have been happy if my predecessor even had used a function. One project had 10k lines... without a single function. I found the same SQL query 13 times in a single file.

Mutable state? What about this other project from a programmer that is now my superior that luckily got replaced by something slightly less bad when i joined the company.

300 global $template, $off, $cat, $lng, $mid, $sub, $sea, $aff, $spe, $da;

895 global $template, $off, $cat, $cat_long, $cat_field, $lang, $mid, $cat_long2, $sfm;
896 global $sea, $seaquery, $lng, $sub, $aff, $spe, $da, $cat_not, $PHP_SELF, $HTTP_HOST;
897 global $q, $_SESSION, $VC_LANG;

1997 global $template, $off, $cat, $cat_long, $cat_field, $lang, $mid, $cat_long2, $sea, $seaquery, $lng, $sub, $spe;

2028 global $template, $scn, $sea, $lng, $sub, $VC_SESSION_C, $off, $aff;
2029 global $allowedxyzewrlhjth3w45z; // Warning DON'T delete or modify
2030 global $stm, $PHP_SELF, $mov, $sfm, $psb, $act, $key, $lang, $fn, $fe, $rn, $re;
2031 global $REMOTE_ADDR, $HTTP_USER_AGENT, $niz, $mid, $cards_key, $fra, $spe;


Or SQL queries like this that were originally in a single line and where i broke up hundreds of similar queries into a slightly more readable format (SQL Formatter vim plugin is a life saver):
+ Show Spoiler +

492 $query = "INSERT INTO movieon4.tmp_movie_detail
493 SELECT m.movie_id,
494 t3.producer_id,
495 t3.producer,
496 m.director,
497 m.produced_year,
498 m.barcode,
499 GROUP_CONCAT(DISTINCT
500 IF(p.propertytype_id = 14,p.property_id,NULL),'|',p.property_text_id,'|',IFNULL(tct.main_category_id,0),'|',IFNULL(p2 .property_text_id,0)
501 SEPARATOR ',')
502 AS movie_category,
503 ROUND((IFNULL(CAST(GROUP_CONCAT(DISTINCT CASE p.property_id
504 WHEN 43 THEN 1
505 WHEN 44 THEN 2
506 WHEN 45 THEN 3
507 WHEN 46 THEN 4
508 WHEN 47 THEN 5
509 END SEPARATOR '') AS decimal),4))) AS sterne,
510 GROUP_CONCAT(DISTINCT IF(p.propertytype_id = 24,p.property_text_id,NULL)) AS sprache,
511 GROUP_CONCAT(DISTINCT p.property_id SEPARATOR ',') REGEXP '^74,|,74,',
512 GROUP_CONCAT(DISTINCT a.actor_id,'|',a.actor SEPARATOR ','),
513 GROUP_CONCAT(DISTINCT IF(p.propertytype_id = 34,p.property_id,NULL)),
514 GROUP_CONCAT(DISTINCT IF(p.propertytype_id = 34,p.property_text_id,NULL)),
515 IFNULL(vs.sum,0),
516 m.aspect_ratio
517 FROM (SELECT DISTINCT movie_id FROM movieon4.tmp_movie WHERE type = 0) tm
518 LEFT JOIN moviedb.movie m ON m.movie_id = tm.movie_id
519 LEFT JOIN moviedb.producer t3 ON t3.producer_id = m.producer_id AND t3.deleted = 0 AND t3.product_id != 5
520 LEFT JOIN moviedb.movieproperty mpp ON tm.movie_id = mpp.movie_id AND mpp.property_id IN (SELECT DISTINCT property_id FROM moviedb.productproperty WHERE product_id IN ( 1, 6, 8, 9, 16, 17, 18, 19, 22 ))
521 LEFT JOIN moviedb.property p ON p.property_id = mpp.property_id AND p.deleted = 0
522 LEFT JOIN movieon4.tmp_vote_statistic vs ON tm.movie_id = vs.movie_id
523 LEFT JOIN movieon4.tmp_category_tree tct ON tct.category_id = p.property_id
524 LEFT JOIN moviedb.property p2 ON p2.property_id = tct.main_category_id AND p2.deleted = 0
525 LEFT JOIN moviedb.actormovie am ON am.movie_id = tm.movie_id
526 LEFT JOIN moviedb.actor a ON a.actor_id = am.actor_id AND a.deleted = 0
527 WHERE 1
528 AND p.propertytype_id in( 14,17,22,23,24,34)
529 GROUP BY m.movie_id

Note that table aliases like 'a' for 'actor', 'm' for 'movie', 'mp' for 'movieproduct' where introduced by me. Before that it was all t1, t2, t3, ... t1000.

I once was an avid reader of thedailywtf.com, then i found out: Such code is actually real and it's the norm, not the exception.
Blisse
Profile Blog Joined July 2010
Canada3710 Posts
Last Edited: 2012-08-29 02:28:57
August 29 2012 02:24 GMT
#3188
+ Show Spoiler +
On August 28 2012 19:04 Leafty wrote:
Show nested quote +
On August 28 2012 10:28 Blisse wrote:
A common example of the list would be, given

a = [1,1,3,2,3,3,2,2]
b = [1,1,2,3,2]

I need the following by the end

a = [2,3,3]
b = []



Why do you expect

a = [2,3,3]
b = []


instead of

a = [3,3,2]
b = []


if you say you expect the order to be preserved?



Sorry, I started adding on elements in the list after I was finished once but I forgot to preserve the order. x.x really stupid mistake on my part.



+ Show Spoiler +
On August 28 2012 17:35 MisterD wrote:
if your language doesn't have established data structures don't use it or write your own :p the dict approach mentioned above basically implements a bag, and you can just as easily get a set by simply associating each key with a fixed value. If you have a bag and set, the implementation becomes pretty straight forward (dirty java snippet using apache commons collections classes):


// inputs..
List a = ...
List b = ...
// count the number of occurances in each array
Bag bagA = new HashBag();
bagA.addAll(a);
Bag bagB = new HashBag();
bagB.addAll(b);
// calculate a set of all different strings for iteration
Set allStrings = new HashSet();
allStrings.addAll(bagA.uniqueSet());
allStrings.addAll(bagB.uniqueSet());
// iterate through all strings
Bag result = new HashBag();
for(String string : allStrings) {
// for each string, store as many copies as the absolute difference in occurance count in a and b
result.add(string, Math.abs(bagA.getCount(string) - bagB.getCount(string));
}
// and done
System.out.println(result);


that runs in linear time and doesn't touch the initial lists/arrays at all except for reading them. I assume you *could* implement this with about 50% less requirements in both time and memory if you really want to, but that just makes the algorithm harder to read, and half of linear is still linear, so it doesn't really matter all that much unless you happen to have real time constraints.



Hmm, this looks like it gets the differences properly, but I want them removed from both sides, not just one. Right now I'm debating whether parsing both arrays separately for differences would be faster than only one.

+ Show Spoiler +

a = [1,2,2,3,4,5,6,6]
b = [6,5,5,4,2,1,7]

results in

a = [2,3,6]
b = [5,7]


That's what my program currently gives, assuming the numbers are actually strings.

This isn't a school project sadly.

Going to try a bunch of your suggestions now. Really appreciate the help guys ^^
There is no one like you in the universe.
Craton
Profile Blog Joined December 2009
United States17246 Posts
Last Edited: 2012-08-29 02:51:44
August 29 2012 02:49 GMT
#3189
Hah. I wish I had queries that small at work. I was fucking around with a 300 line view today which ties into a 75 (100?) line update statement that's joining to something like 7 tables (and naturally that statement is in the middle of a 700ish line procedure which runs a dozen or so updates).

Same old story: vague and changing requirements at the beginning and a lack of time/will by management to scrap code and start over. Trying to just constantly patchwork quilt the damn thing to work for every variation instead of rebuilding on a strong core.

It's certainly an educational experience being thrown into an sprawling, convoluted system straight out of college. Everyone should probably do it once.
+ Show Spoiler +
And then promptly say "fuck this shit" and refactor it from scratch.


Oh, I forgot the best part:
I receive fixed length ASCII files that have over 5000 distinct columns worth of data and not one bit of it is normalized when I receive it.

You know you're having a fun day when your queries involve inner joining 7 900+ column tables
twitch.tv/cratonz
Leafty
Profile Joined July 2012
France84 Posts
Last Edited: 2012-08-29 06:18:41
August 29 2012 05:39 GMT
#3190
I came up with that:

h = {}

i = 0
for x in a:
if not x in h:
h[x] = [[],[]]
h[x][0].append(i)
i += 1

i = 0
for x in b:
if not x in h:
h[x] = [[],[]]
h[x][1].append(i)
i += 1

for k, v in h.iteritems():
m = v[0]
n = v[1]
for i in xrange(min(len(m), len(n))):
a[m[i]] = None
b[n[i]] = None

# Remove all None in a, b
frogmelter
Profile Blog Joined April 2009
United States971 Posts
August 29 2012 05:49 GMT
#3191
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?
TL+ Member
Blisse
Profile Blog Joined July 2010
Canada3710 Posts
Last Edited: 2012-08-29 05:57:42
August 29 2012 05:53 GMT
#3192
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.
There is no one like you in the universe.
frogmelter
Profile Blog Joined April 2009
United States971 Posts
Last Edited: 2012-08-30 06:38:59
August 29 2012 06:21 GMT
#3193
On August 29 2012 14:53 Blisse wrote:
Show nested quote +
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.
TL+ Member
Blisse
Profile Blog Joined July 2010
Canada3710 Posts
Last Edited: 2012-08-29 06:51:38
August 29 2012 06:43 GMT
#3194
On August 29 2012 15:21 frogmelter wrote:
Show nested quote +
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.
There is no one like you in the universe.
tofucake
Profile Blog Joined October 2009
Hyrule19030 Posts
August 29 2012 13:53 GMT
#3195
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?

You only need to check primes up to the square root of the number (so 3037000499 for 9223372036854775805)
Liquipediaasante sana squash banana
frogmelter
Profile Blog Joined April 2009
United States971 Posts
August 29 2012 17:07 GMT
#3196
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.


Ah yeah, this makes a lot more sense. My method was trying to brute force it, which clearly wasn't the intended path. Thanks a bunch.
TL+ Member
zzdd
Profile Joined December 2010
United States484 Posts
August 29 2012 18:00 GMT
#3197
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?

Look up miller-rabin
nakam
Profile Joined April 2010
Sweden245 Posts
August 29 2012 18:54 GMT
#3198
I'm trying to insert multiple rows into a table (MySQL) using prepared statements. So far this is the best working solution I have:

$sql = "INSERT INTO test VALUES(?)";

$values = array('one','two','three');

if ($stmt = $db -> prepare($sql)) {
foreach ($values as $thisValue) {
$stmt -> bind_param("s", $thisValue);
$stmt -> execute();
}
}

Is it possible to insert all values using only one execution or is this the best I can do?
TL Local Timezone Script - http://www.teamliquid.net/forum/viewmessage.php?topic_id=277156
tofucake
Profile Blog Joined October 2009
Hyrule19030 Posts
August 29 2012 18:58 GMT
#3199
$sql = "INSERT INTO test VALUES(?, ?, ?)";
$values = array('one', 'two', 'three');

if($stmt = $db -> prepare($sql)) $stmt->execute($values);
Liquipediaasante sana squash banana
nakam
Profile Joined April 2010
Sweden245 Posts
August 29 2012 19:17 GMT
#3200
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.
TL Local Timezone Script - http://www.teamliquid.net/forum/viewmessage.php?topic_id=277156
Prev 1 158 159 160 161 162 1031 Next
Please log in or register to reply.
Live Events Refresh
Next event in 1h 39m
[ Submit Event ]
Live Streams
Refresh
StarCraft 2
Nina 241
RuFF_SC2 128
Livibee 98
StarCraft: Brood War
Sea 485
NaDa 35
Icarus 1
Dota 2
420jenkins668
capcasts119
NeuroSwarm92
febbydoto10
LuMiX1
League of Legends
JimRising 707
Counter-Strike
Stewie2K678
taco 617
Other Games
summit1g10365
tarik_tv4654
ViBE191
Organizations
Other Games
BasetradeTV70
StarCraft 2
Blizzard YouTube
StarCraft: Brood War
BSLTrovo
sctven
[ Show 16 non-featured ]
StarCraft 2
• Berry_CruncH237
• Hupsaiya 108
• AfreecaTV YouTube
• intothetv
• Kozan
• IndyKCrew
• LaughNgamezSOOP
• Migwel
• sooper7s
StarCraft: Brood War
• Azhi_Dahaki13
• BSLYoutube
• STPLYoutube
• ZZZeroYoutube
League of Legends
• Doublelift4827
• Jankos1655
• masondota21011
Upcoming Events
Korean StarCraft League
1h 39m
CranKy Ducklings
8h 39m
RSL Revival
8h 39m
ByuN vs Cham
herO vs Reynor
FEL
14h 39m
RSL Revival
1d 8h
Clem vs Classic
SHIN vs Cure
FEL
1d 10h
BSL: ProLeague
1d 16h
Dewalt vs Bonyth
Replay Cast
2 days
Sparkling Tuna Cup
3 days
The PondCast
4 days
[ Show More ]
Replay Cast
4 days
RSL Revival
5 days
Replay Cast
5 days
RSL Revival
6 days
Liquipedia Results

Completed

BSL 2v2 Season 3
HSC XXVII
Heroes 10 EU

Ongoing

JPL Season 2
BSL Season 20
Acropolis #3
KCM Race Survival 2025 Season 2
CSL 17: 2025 SUMMER
Copa Latinoamericana 4
Championship of Russia 2025
RSL Revival: Season 1
Murky Cup #2
BLAST.tv Austin Major 2025
ESL Impact League Season 7
IEM Dallas 2025
PGL Astana 2025
Asian Champions League '25
BLAST Rivals Spring 2025
MESA Nomadic Masters
CCT Season 2 Global Finals
IEM Melbourne 2025

Upcoming

2025 ACS Season 2: Qualifier
CSLPRO Last Chance 2025
2025 ACS Season 2
CSLPRO Chat StarLAN 3
K-Championship
uThermal 2v2 Main Event
SEL Season 2 Championship
FEL Cracov 2025
Esports World Cup 2025
StarSeries Fall 2025
FISSURE Playground #2
BLAST Open Fall 2025
BLAST Open Fall Qual
Esports World Cup 2025
BLAST Bounty Fall 2025
BLAST Bounty Fall Qual
IEM Cologne 2025
FISSURE Playground #1
TLPD

1. ByuN
2. TY
3. Dark
4. Solar
5. Stats
6. Nerchio
7. sOs
8. soO
9. INnoVation
10. Elazer
1. Rain
2. Flash
3. EffOrt
4. Last
5. Bisu
6. Soulkey
7. Mini
8. Sharp
Sidebar Settings...

Advertising | Privacy Policy | Terms Of Use | Contact Us

Original banner artwork: Jim Warren
The contents of this webpage are copyright © 2025 TLnet. All Rights Reserved.